A single minimal complement for the c.e. degrees
HTML articles powered by AMS MathViewer
- by Andrew E. M. Lewis PDF
- Trans. Amer. Math. Soc. 359 (2007), 5817-5865 Request permission
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
- C. T. Chong, Generic sets and minimal $\alpha$-degrees, Trans. Amer. Math. Soc. 254 (1979), 157–169. MR 539912, DOI 10.1090/S0002-9947-1979-0539912-0
- S. B. Cooper, Minimal degrees and the jump operator, J. Symbolic Logic 38 (1973), 249–271. MR 347572, DOI 10.2307/2272061
- 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 381964, DOI 10.1090/memo/0162
- Masaru Fukuyama, A remark on minimal degrees, Sci. Rep. Tokyo Kyoiku Daigaku Sect. A 9 (1968), 255–256 (1968). MR 230623
- Andrew Lewis, Minimal complements for degrees below $\mathbf 0’$, J. Symbolic Logic 69 (2004), no. 4, 937–966. MR 2135652, DOI 10.2178/jsl/1102022208
- Andrew Lewis, Finite cupping sets, Arch. Math. Logic 43 (2004), no. 7, 845–858. MR 2096138, DOI 10.1007/s00153-004-0215-5
- 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, DOI 10.1112/S0024611599011818
- Posner, D. 1977 High Degrees, Ph.D. Thesis, University of California, Berkeley.
- David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI 10.2307/2273221
- Seetapun, D. and Slaman, T.A. 1992 Minimal Complements, Unpublished.
- Theodore A. Slaman and John R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160–176. MR 987329, DOI 10.2307/2275022
- 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, DOI 10.1007/978-3-662-02460-7
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI 10.2307/1969604
Additional Information
- Andrew E. M. Lewis
- Affiliation: Dipartimento di Scienze Matematiche ed Informatiche Roberto Magari, Università di Siena, 53100 Siena, Italy
- MR Author ID: 748032
- Email: andy@aemlewis.co.uk, thelewisboy@hotmail.com
- Received by editor(s): August 15, 2002
- Received by editor(s) in revised form: July 22, 2005
- Published electronically: June 26, 2007
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 359 (2007), 5817-5865
- MSC (2000): Primary 03D28
- DOI: https://doi.org/10.1090/S0002-9947-07-04331-0
- MathSciNet review: 2336307