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)

 
 

 

Cupping with random sets


Authors: Adam R. Day and Joseph S. Miller
Journal: Proc. Amer. Math. Soc. 142 (2014), 2871-2879
MSC (2010): Primary 03D32; Secondary 68Q30, 03D30
DOI: https://doi.org/10.1090/S0002-9939-2014-11997-6
Published electronically: April 16, 2014
MathSciNet review: 3209340
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that a set is $ K$-trivial if and only if it is not weakly ML-cuppable. Further, we show that a set below zero jump is $ K$-trivial if and only if it is not ML-cuppable. These results settle a question of Kučera, who introduced both cuppability notions.


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

  • [1] Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies.
    The Denjoy alternative for computable functions. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), 543-554, LIPIcs. Leibniz Int. Proc. Inform., 14, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012. MR 2909344
  • [2] Rod G. Downey and Denis R. Hirschfeldt.
    Algorithmic Randomness and Complexity. Springer-Verlag, 2010. MR 2732288 (2012g:03001)
  • [3] Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin's halting probability, J. Math. Log. 5 (2005), no. 2, 167-192. MR 2188515 (2007e:68031), https://doi.org/10.1142/S0219061305000468
  • [4] Johanna N. Y. Franklin and Keng Meng Ng, Difference randomness, Proc. Amer. Math. Soc. 139 (2011), no. 1, 345-360. MR 2729096 (2012a:03112), https://doi.org/10.1090/S0002-9939-2010-10513-0
  • [5] Denis R. Hirschfeldt, André Nies, and Frank Stephan, Using random sets as oracles, J. Lond. Math. Soc. (2) 75 (2007), no. 3, 610-622. MR 2352724 (2008g:68051), https://doi.org/10.1112/jlms/jdm041
  • [6] Bjørn Kjos-Hanssen, Joseph S. Miller, and Reed Solomon. Lowness notions, measure and domination, J. Lond. Math. Soc. (2) 85 (2012), no. 3, 869-888. MR 2927812
  • [7] Antonín Kučera.
    Measure, $ {\Pi }^0_1$ classes and complete extensions of PA. In H. D. Ebbinghaus, G. H. Müller, and G. E. Sacks, editors, Recursion Theory Week. Proceedings of the Conference held at the Mathematisches Forschungsinstitut in Oberwolfach, April 15-21, 1984; Lecture Notes in Mathematics, vol. 1141, pp. 245-259, Springer, Berlin, 1985. MR 0820784 (87e:03102)
  • [8] Antonín Kučera, On the role of $ {\bf0}'$ in recursion theory, Logic colloquium '86 (Hull, 1986) Stud. Logic Found. Math., vol. 124, North-Holland, Amsterdam, 1988, pp. 133-141. MR 922107 (89b:03070), https://doi.org/10.1016/S0049-237X(09)70655-X
  • [9] Antonín Kučera and Sebastiaan A. Terwijn, Lowness for the class of random sets, J. Symbolic Logic 64 (1999), no. 4, 1396-1402. MR 1780059 (2001j:03082), https://doi.org/10.2307/2586785
  • [10] Joseph S. Miller and André Nies, Randomness and computability: Open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390-410. MR 2248590 (2007c:03059)
  • [11] André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274-305. MR 2166184 (2006j:68052), https://doi.org/10.1016/j.aim.2004.10.006
  • [12] André Nies, Non-cupping and randomness, Proc. Amer. Math. Soc. 135 (2007), no. 3, 837-844. MR 2262880 (2007j:68073), https://doi.org/10.1090/S0002-9939-06-08540-6
  • [13] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883 (2011i:03003)
  • [14] David B. Posner and Robert W. Robinson, Degrees joining to $ {\bf0}^{\prime } $, J. Symbolic Logic 46 (1981), no. 4, 714-722. MR 641485 (83c:03040), https://doi.org/10.2307/2273221
  • [15] Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554 (32 #4013)
  • [16] Stephen G. Simpson, Almost everywhere domination and superhighness, MLQ Math. Log. Q. 53 (2007), no. 4-5, 462-482. MR 2351944 (2009k:03074), https://doi.org/10.1002/malq.200710012
  • [17] Theodore A. Slaman and John R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160-176. MR 987329 (90c:03034), https://doi.org/10.2307/2275022
  • [18] Domenico Zambella. On sequences with simple initial segments, Technical Report ML-1990-05, The Institute for Logic, Language and Computation (ILLC), University of Amsterdam, 1990.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D32, 68Q30, 03D30

Retrieve articles in all journals with MSC (2010): 03D32, 68Q30, 03D30


Additional Information

Adam R. Day
Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720-3840
Address at time of publication: School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington 6140, New Zealand
Email: adam.day@vuw.ac.nz

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
Email: jmiller@math.wisc.edu

DOI: https://doi.org/10.1090/S0002-9939-2014-11997-6
Received by editor(s): June 8, 2012
Received by editor(s) in revised form: August 15, 2012, and August 29, 2012
Published electronically: April 16, 2014
Additional Notes: The first author was supported by a Miller Research Fellowship in the Department of Mathematics at the University of California, Berkeley
The second author was supported by the National Science Foundation under grant No. DMS-1001847.
Communicated by: Julia Knight
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society