A Limit on Relative Genericity in the Recursively Enumerable Sets
Lempp, Steffen ; Slaman, Theodore A.
J. Symbolic Logic, Tome 54 (1989) no. 1, p. 376-395 / Harvested from Project Euclid
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 $\Phi$. 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 $\Phi(-; 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.
Publié le : 1989-06-14
Classification: 
@article{1183742911,
     author = {Lempp, Steffen and Slaman, Theodore A.},
     title = {A Limit on Relative Genericity in the Recursively Enumerable Sets},
     journal = {J. Symbolic Logic},
     volume = {54},
     number = {1},
     year = {1989},
     pages = { 376-395},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742911}
}
Lempp, Steffen; Slaman, Theodore A. A Limit on Relative Genericity in the Recursively Enumerable Sets. J. Symbolic Logic, Tome 54 (1989) no. 1, pp.  376-395. http://gdmltest.u-ga.fr/item/1183742911/