Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A note on the join property

Author: Andrew E. M. Lewis
Journal: Proc. Amer. Math. Soc. 140 (2012), 707-714
MSC (2010): Primary 03D28; Secondary 03D10
Published electronically: June 6, 2011
MathSciNet review: 2846340
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [BC] S.B. Cooper, The strong anticupping property for recursively enumerable degrees, Journal of Symbolic Logic, 54, 527-539, 1989. MR 997886 (91b:03071)
  • [DJS] R. Downey, C.G. Jockusch, M. Stob, Array non-recursive degrees and genericity, Computability, Enumerability, Unsolvability, vol. 224 of the London Mathematical Society Lecture Note Series, 93-104, 1996. MR 1395876 (97f:03060)
  • [N4] R. Downey, N. Greenberg, A.E.M. Lewis, A. Montalbán, Extensions of uppersemilattice embeddings below computably enumerable degrees, to appear.
  • [GMS] N. Greenberg, A. Montalbán, R. Shore, Generalized high degrees have the complementation property, Journal of Symbolic Logic, 69, 1200-1220, 2004. MR 2135663 (2006a:03060)
  • [CJ] C. Jockusch, Degrees of functions with no fixed points, Logic, Methodology, and Philosophy of Science. VIII, edited by J.E. Fenstad, I.T. Frolov, and R. Hilpinen, North-Holland, Amsterdam, New York, Oxford, Tokyo, 191-201, 1989. MR 1034562 (91c:03036)
  • [JS] C. Jockusch and R. Soare, $ \Pi^0_1$ classes and degrees of theories, Transactions of the American Mathematical Society, 173, 33-56, 1972. MR 0316227 (47:4775)
  • [AK] A. Kučera, Measure, $ \Pi^0_1 $-classes and complete extensions of PA, Recursion Theory Week (Oberwolfach, 1984), volume 1141 of Lecture Notes in Math., 245-259, Springer, Berlin, 1985. MR 820784 (87e:03102)
  • [ML] M. Lerman, Degrees of Unsolvability, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1983. MR 708718 (85h:03044)
  • [AL] A. Lewis, On the degree spectrum of a $ \Pi^0_1$ class, Transactions of the American Mathematical Society, 362, 5283-5319, 2010. MR 2657680
  • [AN] A. Nies, Computability and Randomness, Oxford Logic Guides, 51, Oxford University Press, 2009. MR 2548883
  • [PR] D.B. Posner, R.W. Robinson, Degrees joining to $ \boldsymbol{0}'$, Journal of Symbolic Logic, 46, no. 4, 714-722, 1981. MR 641485 (83c:03040)
  • [RR] R.W. Robinson, Degrees joining to $ \boldsymbol{0}'$, Notices of the American Mathematical Society, 19, no. 5, A-615, 1972.
  • [SS] T.A. Slaman, J.R. Steel, Complementation in the Turing degrees, Journal of Symbolic Logic, 54, no. 1, 160-176, 1989. MR 987329 (90c:03034)
  • [RS] R.I. Soare, Recursively enumerable sets and degrees, Springer, New York, 1987. MR 882921 (88m:03003)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D28, 03D10

Retrieve articles in all journals with MSC (2010): 03D28, 03D10

Additional Information

Andrew E. M. Lewis
Affiliation: Department of Pure Mathematics, University of Leeds, Leeds, LS2 9JT, United Kingdom

Received by editor(s): June 28, 2009
Received by editor(s) in revised form: July 15, 2009, August 12, 2010, and November 21, 2010
Published electronically: June 6, 2011
Additional Notes: The author was supported by a Royal Society University Research Fellowship
Communicated by: Julia Knight
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society