Complementation in the Turing Degrees
Slaman, Theodore A. ; Steel, John R.
J. Symbolic Logic, Tome 54 (1989) no. 1, p. 160-176 / Harvested from Project Euclid
Posner [6] has shown, by a nonuniform proof, that every $\triangle^0_2$ degree has a complement below 0'. We show that a 1-generic complement for each $\triangle^0_2$ set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$. In the second half of the paper, we show that the complementation of the degrees below 0' does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees $a$ above $b$ such that no degree strictly below $a$ joins $b$ above $a$. (This result is independently due to S. B. Cooper.) We end with some open problems.
Publié le : 1989-03-14
Classification: 
@article{1183742858,
     author = {Slaman, Theodore A. and Steel, John R.},
     title = {Complementation in the Turing Degrees},
     journal = {J. Symbolic Logic},
     volume = {54},
     number = {1},
     year = {1989},
     pages = { 160-176},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742858}
}
Slaman, Theodore A.; Steel, John R. Complementation in the Turing Degrees. J. Symbolic Logic, Tome 54 (1989) no. 1, pp.  160-176. http://gdmltest.u-ga.fr/item/1183742858/