Complementation in the Turing degrees

Journal of Symbolic Logic 54 (1):160-176 (1989)


Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 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

Download options


    Upload a copy of this work     Papers currently archived: 72,766

External links

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

Through your library


Added to PP

33 (#350,300)

6 months
1 (#386,989)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references

Citations of this work

Dynamic Notions of Genericity and Array Noncomputability.Benjamin Schaeffer - 1998 - Annals of Pure and Applied Logic 95 (1-3):37-69.
Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
Intervals Containing Exactly One C.E. Degree.Guohua Wu - 2007 - Annals of Pure and Applied Logic 146 (1):91-102.
The Minimal Complementation Property Above 0′.Andrew E. M. Lewis - 2005 - Mathematical Logic Quarterly 51 (5):470-492.

View all 6 citations / Add more citations

Similar books and articles

Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
Jump Operator and Yates Degrees.Guohua Wu - 2006 - Journal of Symbolic Logic 71 (1):252 - 264.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
A Hierarchy for the Plus Cupping Turing Degrees.Yong Wang & Angsheng Li - 2003 - Journal of Symbolic Logic 68 (3):972-988.
On a Problem of Cooper and Epstein.Shamil Ishmukhametov - 2003 - Journal of Symbolic Logic 68 (1):52-64.