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

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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2275022
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 60,044
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

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.
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.

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.

Analytics

Added to PP index
2009-01-28

Total views
31 ( #342,504 of 2,433,562 )

Recent downloads (6 months)
1 ( #468,801 of 2,433,562 )

How can I increase my downloads?

Downloads

My notes