A note on the join property

Lewis, Andrew

doi:10.1090/S0002-9939-2011-10908-0

A note on the join property
HTML articles powered by AMS MathViewer

by Andrew E. M. Lewis PDF

Proc. Amer. Math. Soc. 140 (2012), 707-714 Request permission

Abstract:

A Turing degree $\boldsymbol {a}$ satisfies the join property if, for every non-zero $\boldsymbol {b}<\boldsymbol {a}$, there exists $\boldsymbol {c}<\boldsymbol {a}$ with $\boldsymbol {b} \vee \boldsymbol {c}= \boldsymbol {a}$. It was observed by Downey, Greenberg, Lewis and Montalbán that all degrees which are non-GL$_2$ satisfy the join property. This, however, leaves open many questions. Do all a.n.r. degrees satisfy the join property? What about the PA degrees or the Martin-Löf random degrees? A degree $\boldsymbol {b}$ satisfies the cupping property if, for every $\boldsymbol {a}>\boldsymbol {b}$, there exists $\boldsymbol {c}<\boldsymbol {a}$ with $\boldsymbol {b}\vee \boldsymbol {c}=\boldsymbol {a}$. Is satisfying the cupping property equivalent to all degrees above satisfying join? We answer all of these questions by showing that above every low degree there is a low degree which does not satisfy join. We show, in fact, that all low fixed point free degrees $\boldsymbol {a}$ fail to satisfy join and, moreover, that the non-zero degree below $\boldsymbol {a}$ without any joining partner can be chosen to be a c.e. degree.

References

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
Rod Downey, Carl G. Jockusch, and Michael Stob, Array nonrecursive degrees and genericity, Computability, enumerability, unsolvability, London Math. Soc. Lecture Note Ser., vol. 224, Cambridge Univ. Press, Cambridge, 1996, pp. 93–104. MR 1395876, DOI 10.1017/CBO9780511629167.005
R. Downey, N. Greenberg, A.E.M. Lewis, A. Montalbán, Extensions of uppersemilattice embeddings below computably enumerable degrees, to appear.
Noam Greenberg, Antonio Montalbán, and Richard A. Shore, Generalized high degrees have the complementation property, J. Symbolic Logic 69 (2004), no. 4, 1200–1220. MR 2135663, DOI 10.2178/jsl/1102022219
Carl G. Jockusch Jr., Degrees of functions with no fixed points, Logic, methodology and philosophy of science, VIII (Moscow, 1987) Stud. Logic Found. Math., vol. 126, North-Holland, Amsterdam, 1989, pp. 191–201. MR 1034562, DOI 10.1016/S0049-237X(08)70045-4
Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
Thomas Kent and Andrew E. M. Lewis, On the degree spectrum of a $\Pi ^0_1$ class, Trans. Amer. Math. Soc. 362 (2010), no. 10, 5283–5319. MR 2657680, DOI 10.1090/S0002-9947-10-05037-3
André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883, DOI 10.1093/acprof:oso/9780199230761.001.0001
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
R.W. Robinson, Degrees joining to $\boldsymbol {0}’$, Notices of the American Mathematical Society, 19, no. 5, A-615, 1972.
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