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)

 
 

 

$ K$-trivial degrees and the jump-traceability hierarchy


Authors: George Barmpalias, Rod Downey and Noam Greenberg
Journal: Proc. Amer. Math. Soc. 137 (2009), 2099-2109
MSC (2000): Primary 03D80
DOI: https://doi.org/10.1090/S0002-9939-09-09761-5
Published electronically: January 22, 2009
MathSciNet review: 2480292
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For every order $ h$ such that $ \sum_n 1/h(n)$ is finite, every $ K$-trivial degree is $ h$-jump-traceable. This motivated Cholak, Downey and Greenberg to ask whether this traceability property is actually equivalent to $ K$-triviality, thereby giving the hoped for combinatorial characterisation of lowness for Martin-Löf randomness. We show however that the $ K$-trivial degrees are properly contained in those that are $ h$-jump-traceable for every convergent order $ h$.


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

  • 1. George Barmpalias, Andrew E. M. Lewis, and Mariya Soskova.
    Randomness, lowness and degrees.
    J. of Symbolic Logic, 73(2):559-577, 2008. MR 2414465
  • 2. Peter Cholak, Rod Downey, and Noam Greenberg.
    Strong jump-traceability, I: The computably enumerable case.
    Adv. Math., 217:2045-2074, 2008. MR 2388085
  • 3. Rod Downey and Noam Greenberg.
    Strong jump-traceability, II: The general case,
    in preparation.
  • 4. Rod Downey and Denis Hirshfeldt.
    Algorithmic Randomness and Complexity.
    Springer-Verlag, in preparation, 2009.
  • 5. Santiago Figueira, André Nies, and Frank Stephan.
    Lowness properties and approximations of the jump.
    In Proceedings of the 12th Workshop on Logic, Language, Information and Computation (WoLLIC 2005), volume 143 of Electron. Notes Theor. Comput. Sci., pages 45-57 (electronic), Elsevier, Amsterdam, 2006. MR 2270232
  • 6. Bjørn Kjos-Hanssen.
    Low for random reals and positive-measure domination.
    Proc. Amer. Math. Soc., 135(11):3703-3709 (electronic), 2007. MR 2336587 (2008g:03070)
  • 7. Bjørn Kjos-Hanssen, André Nies, and Frank Stephan.
    Lowness for the class of Schnorr random reals.
    SIAM J. Comput., 35(3):647-657 (electronic), 2005. MR 2201451 (2006j:68051)
  • 8. Joseph S. Miller and André Nies.
    Randomness and computability: Open questions.
    Bull. Symbolic Logic, 12(3):390-410, 2006. MR 2248590 (2007c:03059)
  • 9. A. Nies.
    Reals which compute little.
    In Logic Colloquium '02, Lecture Notes in Logic, 27, pages 261-275, Assoc. Symbol. Logic, La Jolla, CA, 2006. MR 2258710 (2007i:03048)
  • 10. André Nies.
    Lowness properties and randomness.
    Adv. Math., 197(1):274-305, 2005. MR 2166184 (2006j:68052)
  • 11. André Nies.
    Eliminating concepts.
    In Proceedings of the IMS workshop on computational aspects of infinity, Singapore, to appear, 2008.
  • 12. André Nies.
    Computability and Randomness.
    Oxford University Press, in preparation, 2009.
  • 13. Keng-Meng Ng.
    Beyond jump traceability,
    preprint.
  • 14. S. Terwijn and D. Zambella.
    Algorithmic randomness and lowness.
    J. Symbolic Logic, 66:1199-1205, 2001. MR 1856736 (2002j:03044)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03D80

Retrieve articles in all journals with MSC (2000): 03D80


Additional Information

George Barmpalias
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: George.Barmpalias@mcs.vuw.ac.nz

Rod Downey
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: downey@mcs.vuw.ac.nz

Noam Greenberg
Affiliation: School of Mathematics, Statistics and Computer Science, Victoria University, P.O. Box 600, Wellington, New Zealand
Email: greenberg@mcs.vuw.ac.nz

DOI: https://doi.org/10.1090/S0002-9939-09-09761-5
Keywords: K-triviality, Turing degrees, jump traceability, superlinear orders
Received by editor(s): March 20, 2008
Received by editor(s) in revised form: September 11, 2008
Published electronically: January 22, 2009
Additional Notes: All authors were supported by the Marsden Fund of New Zealand.
Communicated by: Julia Knight
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society