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

DOI:
https://doi.org/10.1090/S0002-9939-2012-11183-9

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.

**[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 -generic degree with a strong minimal cover.*J. Symbolic Logic*, 65(3):1395-1442, 2000. MR**1791382 (2001m:03080)****[Lew07a]**Andrew E. M. Lewis.

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)**

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

Email:
barmpalias@gmail.com

**Andrew E. M. Lewis**

Affiliation:
School of Mathematics, University of Leeds, LS2 9JT Leeds, United Kingdom

Email:
andy@aemlewis.com

DOI:
https://doi.org/10.1090/S0002-9939-2012-11183-9

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