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

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 such that for all non-zero c.e. degrees , . Since is minimal this means that complements all c.e. degrees other than and . Since every -c.e. degree bounds a non-zero c.e. degree, complements every -c.e. degree other than and .

**[CC]**C. T. Chong,*Generic sets and minimal 𝛼-degrees*, Trans. Amer. Math. Soc.**254**(1979), 157–169. MR**539912**, 10.1090/S0002-9947-1979-0539912-0**[BC]**S. B. Cooper,*Minimal degrees and the jump operator*, J. Symbolic Logic**38**(1973), 249–271. MR**0347572****[RE]**Richard L. Epstein,*Minimal degrees of unsolvability and the full approximation construction*, Mem. Amer. Math. Soc.**3**(1975), no. iss.1, 162, viii+136. MR**0381964****[MF]**Masaru Fukuyama,*A remark on minimal degrees*, Sci. Rep. Tokyo Kyoiku Daigaku Sect. A**9**(1968), 255–256 (1968). MR**0230623****[AL1]**Andrew Lewis,*Minimal complements for degrees below 0’*, J. Symbolic Logic**69**(2004), no. 4, 937–966. MR**2135652**, 10.2178/jsl/1102022208**[AL2]**Andrew Lewis,*Finite cupping sets*, Arch. Math. Logic**43**(2004), no. 7, 845–858. MR**2096138**, 10.1007/s00153-004-0215-5**[LY]**Angsheng Li and Xiaoding Yi,*Cupping the recursively enumerable degrees by d.r.e. degrees*, Proc. London Math. Soc. (3)**79**(1999), no. 1, 1–21. MR**1687559**, 10.1112/S0024611599011818**[DP1]**Posner, D. 1977*High Degrees*, Ph.D. Thesis, University of California, Berkeley.**[PR]**David B. Posner and Robert W. Robinson,*Degrees joining to 0′*, J. Symbolic Logic**46**(1981), no. 4, 714–722. MR**641485**, 10.2307/2273221**[SS1]**Seetapun, D. and Slaman, T.A. 1992*Minimal Complements*, Unpublished.**[SSt]**Theodore A. Slaman and John R. Steel,*Complementation in the Turing degrees*, J. Symbolic Logic**54**(1989), no. 1, 160–176. MR**987329**, 10.2307/2275022**[RS1]**Robert I. Soare,*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921****[CS]**Clifford Spector,*On degrees of recursive unsolvability*, Ann. of Math. (2)**64**(1956), 581–592. MR**0082457**

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.