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)



Measure and cupping in the Turing degrees

Authors: George Barmpalias and Andrew E. M. Lewis
Journal: Proc. Amer. Math. Soc. 140 (2012), 3607-3622
MSC (2010): Primary 03D28; Secondary 03D10
Published electronically: February 6, 2012
MathSciNet review: 2929029
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We answer a question of Jockusch by showing that the measure of the Turing degrees that satisfy the cupping property is 0. In fact, every 2-random degree has a strong minimal cover and so fails to satisfy the cupping property.

References [Enhancements On Off] (What's this?)

  • [BDN11] George Barmpalias, Rod Downey, and Keng-Meng Ng.
    Jump inversions inside effectively closed sets and applications to randomness.
    J. Symbolic Logic, 2011.
    In press.
  • [Coo04] S. Barry Cooper.
    Computability Theory.
    CRC Mathematics Series. Chapman & Hall, Boca Raton, FL, New York, London, 2004. MR 2017461 (2005h:03001)
  • [DH10] Rod Downey and Denis Hirschfeldt.
    Algorithmic Randomness and Complexity.
    Springer-Verlag, 2010. MR 2732288
  • [DJS96] Rod Downey, Carl G. Jockusch, Jr., and Michael Stob.
    Array nonrecursive sets and genericity.
    In Computability, Enumerability, Unsolvability: Directions in Recursion Theory, volume 224 of London Mathematical Society Lecture Notes Series, pages 93-104. Cambridge University Press, 1996. MR 1395876 (97f:03060)
  • [Joc80] C. Jockusch, Jr.
    Degrees of generic sets.
    In F. R. Drake and S. S. Wainer, editors, Recursion Theory: Its Generalizations and Applications, Proceedings of Logic Colloquium '79, Leeds, August 1979, pages 110-139, Cambridge University Press, Cambridge, U. K., 1980. MR 598304 (83i:03070)
  • [Kum00] Masahiro Kumabe.
    A $ 1$-generic degree with a strong minimal cover.
    J. Symbolic Logic, 65(3):1395-1442, 2000. MR 1791382 (2001m:03080)
  • [Lew07a] Andrew E. M. Lewis.
    $ \Pi _1^0$ classes, strong minimal covers and hyperimmune-free degrees.
    Bull. Lond. Math. Soc., 39(6):892-910, 2007. MR 2392813 (2009b:03113)
  • [Lew07b] Andrew E. M. Lewis.
    A random degree with strong minimal cover.
    Bull. Lond. Math. Soc., 39(5):848-856, 2007. MR 2365234 (2008i:03049)
  • [Lew09] Andrew E. M. Lewis.
    Strong minimal covers and a question of Yates: the story so far.
    In Logic Colloquium 2006, Lect. Notes Log., pages 213-228. Assoc. Symbol. Logic, Chicago, IL, 2009. MR 2562554 (2010j:03039)
  • [Mar0s] D. Martin.
    Measure, category, and degrees of unsolvability.
    Unpublished manuscript, 1960s.
  • [ML66] Per Martin-Löf.
    The definition of random sequences.
    Information and Control, 9:602-619, 1966. MR 0223179 (36:6228)
  • [Nie09] André Nies.
    Computability and Randomness.
    Oxford University Press, 2009. MR 2548883
  • [Sac63] G. E. Sacks.
    Degrees of Unsolvability, volume 55 of Annals of Mathematical Studies.
    Princeton University Press, 1963. MR 0186554 (32:4013)
  • [Soa87] 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 (88m:03003)
  • [Spe56] C. Spector.
    On the degrees of recursive unsolvability.
    Ann. of Math. (2), 64:581-592, 1956. MR 0082457 (18:552d)

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

George Barmpalias
Affiliation: Institute for Logic, Language and Computation, Universiteit van Amsterdam 1090 GE, P.O. Box 94242, The Netherlands

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

Received by editor(s): January 24, 2011
Received by editor(s) in revised form: March 11, 2011, and April 5, 2011
Published electronically: February 6, 2012
Additional Notes: The second author was supported by a Royal Society University Research Fellowship.
Communicated by: Julia Knight
Article copyright: © Copyright 2012 American Mathematical Society

American Mathematical Society