Complementation in the Turing degrees

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,560

External links

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

Through your library

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.

Analytics

Added to PP
2009-01-28

Downloads
35 (#390,377)

6 months
2 (#646,201)

Historical graph of downloads
How can I increase my downloads?

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.
Generic degrees are complemented.Masahiro Kumabe - 1993 - Annals of Pure and Applied Logic 59 (3):257-272.
Quasi-complements of the cappable degrees.Guohua Wu - 2004 - Mathematical Logic Quarterly 50 (2):189.

View all 7 citations / Add more citations

References found in this work

No references found.

Add more references