A limit on relative genericity in the recursively enumerable sets
Journal of Symbolic Logic 54 (2):376-395 (1989)
| Abstract | Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,709 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesDev K. Roy (1993). Recursive Versus Recursively Enumerable Binary Relations. Studia Logica 52 (4):587 - 593.
Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
Iraj Kalantari & Allen Retzlaff (1979). Recursive Constructions in Topological Spaces. Journal of Symbolic Logic 44 (4):609-625.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
Peter Cholak, Marcia Groszek & Theodore Slaman (2001). An Almost Deep Degree. Journal of Symbolic Logic 66 (2):881-901.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Stephan Wehner (1999). On Recursive Enumerability with Finite Repetitions. Journal of Symbolic Logic 64 (3):927-945.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
Michael E. Mytilinaios & Theodore A. Slaman (1988). Σ2-Collection and the Infinite Injury Priority Method. Journal of Symbolic Logic 53 (1):212 - 221.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
