Possible degrees in recursive copies

Annals of Pure and Applied Logic 75 (3):215-221 (1995)
  Copy   BIBTEX

Abstract

Let be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this is not the case. Here we give examples illustrating some restrictions on the possible ∑α0 degrees. In these examples, the image of R cannot be ∑α0 of degree d unless d possesses an “α-table”

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,122

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Possible degrees in recursive copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
Degrees joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
Minimal degrees recursive in 1-generic degrees.C. T. Chong & R. G. Downey - 1990 - Annals of Pure and Applied Logic 48 (3):215-225.
Lowness for Kurtz randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
The Ackermann functions are not optimal, but by how much?H. Simmons - 2010 - Journal of Symbolic Logic 75 (1):289-313.
Inseparability in recursive copies.Kevin J. Davey - 1994 - Annals of Pure and Applied Logic 68 (1):1-52.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
Infima of d.r.e. degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.

Analytics

Added to PP
2014-01-16

Downloads
18 (#747,034)

6 months
5 (#366,001)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Possible degrees in recursive copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
Coding a family of sets.J. F. Knight - 1998 - Annals of Pure and Applied Logic 94 (1-3):127-142.
Generalized weak presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.

View all 6 citations / Add more citations

References found in this work

Degrees of Unsolvability.Gerald E. Sacks - 1966 - Princeton University Press.
Ramified systems.C. J. Ash & J. F. Knight - 1994 - Annals of Pure and Applied Logic 70 (3):205-221.

Add more references