|
Measure and cupping in the Turing degrees
Authors:
George Barmpalias and Andrew E. M. Lewis
Journal:
Proc. Amer. Math. Soc.
MSC (2010):
Primary 03D28; Secondary 03D10
Posted:
February 6, 2012
Full-text PDF
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
- [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, Chapman & Hall/CRC,
Boca Raton, FL, 2004. MR 2017461
(2005h:03001)
- [DH10]
Rodney
G. Downey and Denis
R. Hirschfeldt, Algorithmic randomness and complexity, Theory
and Applications of Computability, Springer, New York, 2010. MR
2732288
- [DJS96]
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
(97f:03060), http://dx.doi.org/10.1017/CBO9780511629167.005
- [Joc80]
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, 1980, pp. 110–139. MR 598304
(83i:03070)
- [Kum00]
Masahiro
Kumabe, A 1-generic degree with a strong minimal cover, J.
Symbolic Logic 65 (2000), no. 3, 1395–1442. MR 1791382
(2001m:03080), http://dx.doi.org/10.2307/2586706
- [Lew07a]
Andrew
E. M. Lewis, Π₁⁰ classes, strong minimal covers
and hyperimmune-free degrees, Bull. Lond. Math. Soc.
39 (2007), no. 6, 892–910. MR 2392813
(2009b:03113), http://dx.doi.org/10.1112/blms/bdm083
- [Lew07b]
Andrew
E. M. Lewis, A random degree with strong minimal cover, Bull.
Lond. Math. Soc. 39 (2007), no. 5, 848–856. MR 2365234
(2008i:03049), http://dx.doi.org/10.1112/blms/bdm074
- [Lew09]
Andrew
E. M. Lewis, Strong minimal covers and a question of Yates: the
story so far, Logic Colloquium 2006, Lect. Notes Log., Assoc. Symbol.
Logic, Chicago, IL, 2009, pp. 213–228. MR 2562554
(2010j:03039), http://dx.doi.org/10.1017/CBO9780511605321.011
- [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 (1966), 602–619. MR 0223179
(36 #6228)
- [Nie09]
André
Nies, Computability and randomness, Oxford Logic Guides,
vol. 51, Oxford University Press, Oxford, 2009. MR 2548883
(2011i:03003)
- [Sac63]
Gerald
E. Sacks, Degrees of unsolvability, Princeton University
Press, Princeton, N.J., 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]
Clifford
Spector, On degrees of recursive unsolvability, Ann. of Math.
(2) 64 (1956), 581–592. 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
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:
http://dx.doi.org/10.1090/S0002-9939-2012-11183-9
PII:
S 0002-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
Posted:
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
|
