Available in electronic format
Available in print format		 Transacrions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

A single minimal complement for the c.e. degrees

Author(s): Andrew E. M. Lewis
Journal: Trans. Amer. Math. Soc. 359 (2007), 5817-5865.
MSC (2000): Primary 03D28
Posted: June 26, 2007
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: We show that there exists a minimal (Turing) degree $ b<0' $ such that for all non-zero c.e. degrees $ a $, $ 0'=a\vee b $. Since $ b$ is minimal this means that $ b $ complements all c.e. degrees other than $ 0 $ and $ 0' $. Since every $ n $-c.e. degree bounds a non-zero c.e. degree, $ b $ complements every $ n $-c.e. degree other than $ 0 $ and $ 0' $.

References:

[CC]
Chong, C.T. 1979 Generic sets and minimal $ \alpha$-degrees, Trans. Amer. Math. Soc. 254, 157-169. MR 0539912 (81c:03037)

[BC]
Cooper, S.B. 1973 Minimal degrees and the jump operator, J. Symbolic Logic 38, 249-271. MR 0347572 (50:75)

[RE]
Epstein, R.L. 1975 Minimal degrees of unsolvability and the full approximation construction, Memoirs of the American Mathematical Society, no. 163. MR 0381964 (52:2853)

[MF]
Fukuyama, M. 1968 A remark on minimal degrees, Sci. Rep. Tokyo. Daig. 9, 255-256. MR 0230623 (37:6183)

[AL1]
Lewis, A.E.M. Minimal Complements For Degrees Below $ 0' $, J. Symbolic Logic, 69 (2004), 937-966. MR 2135652 (2005m:03087)

[AL2]
Lewis, A.E.M. Finite Cupping Sets, Archive Math. Logic 43 (2004), 845-858. MR 2096138 (2005e:03094)

[LY]
Li, A. and Yi, X. 1999 Cupping the recursively enumerable degrees by d-r.e. degrees, Proc. Lond. Math. Soc. 78, 1-21. MR 1687559 (2000f:03122)

[DP1]
Posner, D. 1977 High Degrees, Ph.D. Thesis, University of California, Berkeley.

[PR]
Posner, D. and Robinson, R.W. 1981 Degrees joining to $ 0' $, J. Symbolic Logic 46, 714-722. MR 0641485 (83c:03040)

[SS1]
Seetapun, D. and Slaman, T.A. 1992 Minimal Complements, Unpublished.

[SSt]
Slaman, T.A. and Steel, J. 1989 Complementation in the Turing degrees, J. Symbolic Logic 54, 160-176. MR 0987329 (90c:03034)

[RS1]
Soare, R.I. 1987 Recursively Enumerable Sets and Degrees, Springer, New York. MR 0882921 (88m:03003)

[CS]
Spector, C. 1956 On degrees of recursive unsolvability , Ann. Math. 64, 581-592. MR 0082457 (18:552d)

Similar Articles:

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D28

Retrieve articles in all Journals with MSC (2000): 03D28

Additional Information:

Andrew E. M. Lewis
Affiliation: Dipartimento di Scienze Matematiche ed Informatiche Roberto Magari, Università di Siena, 53100 Siena, Italy
Email: andy@aemlewis.co.uk, thelewisboy@hotmail.com

DOI: 10.1090/S0002-9947-07-04331-0
PII: S 0002-9947(07)04331-0
Received by editor(s): August 15, 2002
Received by editor(s) in revised form: July 22, 2005
Posted: June 26, 2007
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google