Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

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
MathSciNet review: 2336307
Retrieve article in: PDF

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 and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia