Inherent enumerability of strong jump-traceability

Diamondstone, David; Greenberg, Noam; Turetsky, Daniel

doi:10.1090/S0002-9947-2014-06089-3

Inherent enumerability of strong jump-traceability
HTML articles powered by AMS MathViewer

by David Diamondstone, Noam Greenberg and Daniel D. Turetsky PDF

Trans. Amer. Math. Soc. 367 (2015), 1771-1796 Request permission

Abstract:

We show that every strongly jump-traceable set obeys every benign cost function. Moreover, we show that every strongly jump-traceable set is computable from a computably enumerable strongly jump-traceable set. This allows us to generalise properties of c.e. strongly jump-traceable sets to all such sets. For example, the strongly jump-traceable sets induce an ideal in the Turing degrees; the strongly jump-traceable sets are precisely those that are computable from all superlow Martin-Löf random sets; the strongly jump-traceable sets are precisely those that are a base for $\mathrm {Demuth}_{\mathrm {BLR}}$ randomness; and strong jump-traceability is equivalent to strong superlowness.

References

George Barmpalias, Rod Downey, and Noam Greenberg, $K$-trivial degrees and the jump-traceability hierarchy, Proc. Amer. Math. Soc. 137 (2009), no. 6, 2099–2109. MR 2480292, DOI 10.1090/S0002-9939-09-09761-5
Laurent Bienvenu, Adam R. Day, Noam Greenberg, Antonín Kučera, Joseph S. Miller, André Nies, and Dan Turetsky, Computing $K$-trivial sets by incomplete random sets, Bull. Symb. Log. 20 (2014), no. 1, 80–90. MR 3230826, DOI 10.1017/bsl.2013.3
Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies, and Dan Turetsky, Characterizing lowness for Demuth randomness, J. Symb. Log. 79 (2014), no. 2, 526–560. MR 3224979, DOI 10.1017/jsl.2013.21
Gregory J. Chaitin, Information-theoretic characterizations of recursive infinite strings, Theoret. Comput. Sci. 2 (1976), no. 1, 45–48. MR 413595, DOI 10.1016/0304-3975(76)90005-0
Gregory J. Chaitin, Nonrecursive infinite strings with simple initial segments, IBM Journal of Research and Development 21 (1977), 350–359.
Peter Cholak, Rod Downey, and Noam Greenberg, Strong jump-traceabilty. I. The computably enumerable case, Adv. Math. 217 (2008), no. 5, 2045–2074. MR 2388085, DOI 10.1016/j.aim.2007.09.008
Rod Downey and Noam Greenberg, Strong jump-traceability II: $K$-triviality, Israel J. Math. 191 (2012), no. 2, 647–665. MR 3011490, DOI 10.1007/s11856-011-0217-z
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 G. Downey, Denis R. Hirschfeldt, André Nies, and Frank Stephan, Trivial reals, Proceedings of the 7th and 8th Asian Logic Conferences, Singapore Univ. Press, Singapore, 2003, pp. 103–131. MR 2051976, DOI 10.1142/9789812705815_{0}005
Rod Downey, Denis R. Hirschfeldt, André Nies, and Sebastiaan A. Terwijn, Calibrating randomness, Bull. Symbolic Logic 12 (2006), no. 3, 411–491. MR 2248591
Santiago Figueira, André Nies, and Frank Stephan, Lowness properties and approximations of the jump, Ann. Pure Appl. Logic 152 (2008), no. 1-3, 51–66. MR 2397489, DOI 10.1016/j.apal.2007.11.002
Noam Greenberg, Denis R. Hirschfeldt, and André Nies, Characterizing the strongly jump-traceable sets via randomness, Adv. Math. 231 (2012), no. 3-4, 2252–2293. MR 2964638, DOI 10.1016/j.aim.2012.06.005
Noam Greenberg and André Nies, Benign cost functions and lowness properties, J. Symbolic Logic 76 (2011), no. 1, 289–312. MR 2791349, DOI 10.2178/jsl/1294171001
Noam Greenberg and Daniel D. Turetsky, Strong jump-traceability and Demuth randomness, Proc. Lond. Math. Soc. (3) 108 (2014), no. 3, 738–779. MR 3180595, DOI 10.1112/plms/pdt040
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, DOI 10.1112/jlms/jdm041
Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle, Time-bounded Kolmogorov complexity and Solovay functions, Mathematical foundations of computer science 2009, Lecture Notes in Comput. Sci., vol. 5734, Springer, Berlin, 2009, pp. 392–402. MR 2539508, DOI 10.1007/978-3-642-03816-7_{3}4
Antonín Kučera and André Nies, Demuth randomness and computational complexity, Ann. Pure Appl. Logic 162 (2011), no. 7, 504–513. MR 2781092, DOI 10.1016/j.apal.2011.01.004
Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590
Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166. MR 228341, DOI 10.1002/malq.19680140704
Keng Meng Ng, On strongly jump traceable reals, Ann. Pure Appl. Logic 154 (2008), no. 1, 51–69. MR 2413929, DOI 10.1016/j.apal.2007.11.014
André Nies, Lowness properties and randomness, Adv. Math. 197 (2005), no. 1, 274–305. MR 2166184, DOI 10.1016/j.aim.2004.10.006
André Nies, Eliminating concepts, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 225–247. MR 2449467, DOI 10.1142/9789812796554_{0}012
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
André Nies, Computably enumerable sets below random sets, Ann. Pure Appl. Logic 163 (2012), no. 11, 1596–1610. MR 2959662, DOI 10.1016/j.apal.2011.12.011
André Nies, Calculus of cost functions. In preparation.
Jean Raisonnier, A mathematical proof of S. Shelah’s theorem on the measure problem and related results, Israel J. Math. 48 (1984), no. 1, 48–56. MR 768265, DOI 10.1007/BF02760523
Robert M. Solovay, Draft of paper (or series of papers) related to Chaitin’s work. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages, 1975.
Sebastiaan A. Terwijn, Computability and Measure. PhD thesis, University of Amsterdam, 1998.
Sebastiaan A. Terwijn and Domenico Zambella, Computational randomness and lowness, J. Symbolic Logic 66 (2001), no. 3, 1199–1205. MR 1856736, DOI 10.2307/2695101