Measure and cupping in the Turing degrees

Barmpalias, George; Lewis, Andrew

doi:10.1090/S0002-9939-2012-11183-9

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