Measure and cupping in the Turing degrees
HTML articles powered by AMS MathViewer
- by George Barmpalias and Andrew E. M. Lewis PDF
- Proc. Amer. Math. Soc. 140 (2012), 3607-3622 Request permission
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
- George Barmpalias, Rod Downey, and Keng-Meng Ng. Jump inversions inside effectively closed sets and applications to randomness. J. Symbolic Logic, 2011. In press.
- S. Barry Cooper, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004. MR 2017461
- Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288, DOI 10.1007/978-0-387-68441-3
- 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
- Carl G. Jockusch Jr., Degrees of generic sets, Recursion theory: its generalisation and applications (Proc. Logic Colloq., Univ. Leeds, Leeds, 1979) London Math. Soc. Lecture Note Ser., vol. 45, Cambridge Univ. Press, Cambridge-New York, 1980, pp. 110–139. MR 598304
- Masahiro Kumabe, A $1$-generic degree with a strong minimal cover, J. Symbolic Logic 65 (2000), no. 3, 1395–1442. MR 1791382, DOI 10.2307/2586706
- Andrew E. M. Lewis, $\Pi _1^0$ classes, strong minimal covers and hyperimmune-free degrees, Bull. Lond. Math. Soc. 39 (2007), no. 6, 892–910. MR 2392813, DOI 10.1112/blms/bdm083
- Andrew E. M. Lewis, A random degree with strong minimal cover, Bull. Lond. Math. Soc. 39 (2007), no. 5, 848–856. MR 2365234, DOI 10.1112/blms/bdm074
- Andrew E. M. Lewis, Strong minimal covers and a question of Yates: the story so far, Logic Colloquium 2006, Lect. Notes Log., vol. 32, Assoc. Symbol. Logic, Chicago, IL, 2009, pp. 213–228. MR 2562554, DOI 10.1017/CBO9780511605321.011
- D. Martin. Measure, category, and degrees of unsolvability. Unpublished manuscript, 1960s.
- Per Martin-Löf, The definition of random sequences, Information and Control 9 (1966), 602–619. MR 223179
- 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
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- 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
Additional Information
- George Barmpalias
- Affiliation: Institute for Logic, Language and Computation, Universiteit van Amsterdam 1090 GE, P.O. Box 94242, The Netherlands
- Email: barmpalias@gmail.com
- Andrew E. M. Lewis
- Affiliation: School of Mathematics, University of Leeds, LS2 9JT Leeds, United Kingdom
- MR Author ID: 748032
- Email: andy@aemlewis.com
- 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
- © Copyright 2012 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 140 (2012), 3607-3622
- MSC (2010): Primary 03D28; Secondary 03D10
- DOI: https://doi.org/10.1090/S0002-9939-2012-11183-9
- MathSciNet review: 2929029