Archive for Mathematical Logic 33 (5):321-346 (1994)

A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W e X . The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA degree, then for alln there exists an-r.e.[C] setA such thatA ⊕C is not of (m+n)-REA degree. We conjecture that this holds also form≥2
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/BF01278463
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,259
Through your library

References found in this work BETA

Add more references

Citations of this work BETA

Isolation in the CEA Hierarchy.Geoffrey LaForte - 2005 - Archive for Mathematical Logic 44 (2):227-244.

Add more citations

Similar books and articles

Array Nonrecursiveness and Relative Recursive Enumerability.Mingzhong Cai - 2012 - Journal of Symbolic Logic 77 (1):21-32.
Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.
Relative Enumerability and 1-Genericity.Wei Wang - 2011 - Journal of Symbolic Logic 76 (3):897 - 913.
On the Cantor-Bendixon Rank of Recursively Enumerable Sets.Peter Cholak & Rod Downey - 1993 - Journal of Symbolic Logic 58 (2):629-640.
On Relative Enumerability of Turing Degrees.Shamil Ishmukhametov - 2000 - Archive for Mathematical Logic 39 (3):145-154.
On the R.E. Predecessors of D.R.E. Degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.
Recursive Analysis.R. L. Goodstein - 1961 - Dover Publications.
The Ackermann Functions Are Not Optimal, but by How Much?H. Simmons - 2010 - Journal of Symbolic Logic 75 (1):289-313.
Degrees Joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
Relative Recursive Enumerability of Generic Degrees.Masahiro Kumabe - 1991 - Journal of Symbolic Logic 56 (3):1075-1084.


Added to PP index

Total views
51 ( #224,103 of 2,518,587 )

Recent downloads (6 months)
1 ( #408,186 of 2,518,587 )

How can I increase my downloads?


My notes