A single minimal complement for the c.e. degrees

Lewis, Andrew

doi:10.1090/S0002-9947-07-04331-0

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