Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

A single minimal complement for the c.e. degrees


Author: Andrew E. M. Lewis
Journal: Trans. Amer. Math. Soc. 359 (2007), 5817-5865
MSC (2000): Primary 03D28
DOI: https://doi.org/10.1090/S0002-9947-07-04331-0
Published electronically: June 26, 2007
MathSciNet review: 2336307
Full-text PDF Free Access

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 [Enhancements On Off] (What's this?)

  • [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: https://doi.org/10.1090/S0002-9947-07-04331-0
Received by editor(s): August 15, 2002
Received by editor(s) in revised form: July 22, 2005
Published electronically: June 26, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society