Computably enumerable Turing degrees and the meet property

Durrant, Benedict; Lewis-Pye, Andy; Ng, Keng Meng; Riley, James

doi:10.1090/proc/12808

Computably enumerable Turing degrees and the meet property
HTML articles powered by AMS MathViewer

by Benedict Durrant, Andy Lewis-Pye, Keng Meng Ng and James Riley

Proc. Amer. Math. Soc. 144 (2016), 1735-1744

DOI: https://doi.org/10.1090/proc/12808

Published electronically: August 12, 2015

PDF | Request permission

Abstract:

Working in the Turing degree structure, we show that those degrees which contain computably enumerable sets all satisfy the meet property, i.e. if $\boldsymbol {a}$ is c.e. and $\boldsymbol {b}<\boldsymbol {a}$, then there exists non-zero $\boldsymbol {m}<\boldsymbol {a}$ with $\boldsymbol {b} \wedge \boldsymbol {m}= \boldsymbol {0}$. In fact, more than this is true: $\boldsymbol {m}$ may always be chosen to be a minimal degree. This settles a conjecture of Cooper and Epstein from the 1980s.

References

S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
S. B. Cooper, Some negative results on minimal degrees below $\boldsymbol {0}’$, Recursive Function Theory Newsletter, 34, item 353.
S. Barry Cooper, Local degree theory, Handbook of computability theory, Stud. Logic Found. Math., vol. 140, North-Holland, Amsterdam, 1999, pp. 121–153. MR 1720771, DOI 10.1016/S0049-237X(99)80020-2
S. B. Cooper, The strong anticupping property for recursively enumerable degrees, J. Symbolic Logic 54 (1989), no. 2, 527–539. MR 997886, DOI 10.2307/2274867
S. Barry Cooper and Richard L. Epstein, Complementing below recursively enumerable degrees, Ann. Pure Appl. Logic 34 (1987), no. 1, 15–32. MR 887552, DOI 10.1016/0168-0072(87)90039-X
Richard L. Epstein, Degrees of unsolvability: structure and theory, Lecture Notes in Mathematics, vol. 759, Springer, Berlin, 1979. MR 551620
Richard L. Epstein, Initial segments of degrees below ${\bf 0}^{\prime }$, Mem. Amer. Math. Soc. 30 (1981), no. 241, vi+102. MR 603392, DOI 10.1090/memo/0241
Shamil Ishmukhametov, On a problem of Cooper and Epstein, J. Symbolic Logic 68 (2003), no. 1, 52–64. MR 1959312, DOI 10.2178/jsl/1045861506
S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
A. E. M. Lewis, The search for natural definability in the Turing degrees, submitted.
Andrew E. M. Lewis, Properties of the jump classes, J. Logic Comput. 22 (2012), no. 4, 845–855. MR 2956020, DOI 10.1093/logcom/exq047
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
Angsheng Li and Dong-Ping Yang, Bounding minimal degrees by computably enumerable degrees, J. Symbolic Logic 63 (1998), no. 4, 1319–1347. MR 1665723, DOI 10.2307/2586653
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
A. M. Turing, Systems of Logic Based on Ordinals, Proc. London Math. Soc. (2) 45 (1939), no. 3, 161–228. MR 1576807, DOI 10.1112/plms/s2-45.1.161