Cupping with random sets

Day, Adam; Miller, Joseph

doi:10.1090/S0002-9939-2014-11997-6

Cupping with random sets
HTML articles powered by AMS MathViewer

by Adam R. Day and Joseph S. Miller PDF

Proc. Amer. Math. Soc. 142 (2014), 2871-2879 Request permission

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

Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller, and André Nies, The Denjoy alternative for computable functions, 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 14, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012, pp. 543–554. MR 2909344
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 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, DOI 10.1142/S0219061305000468
Johanna N. Y. Franklin and Keng Meng Ng, Difference randomness, Proc. Amer. Math. Soc. 139 (2011), no. 1, 345–360. MR 2729096, DOI 10.1090/S0002-9939-2010-10513-0
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
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, DOI 10.1112/jlms/jdr072
Antonín Kučera, Measure, $\Pi ^0_1$-classes and complete extensions of $\textrm {PA}$, Recursion theory week (Oberwolfach, 1984) Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259. MR 820784, DOI 10.1007/BFb0076224
Antonín Kučera, On the role of ${\bf 0}’$ in recursion theory, Logic colloquium ’86 (Hull, 1986) Stud. Logic Found. Math., vol. 124, North-Holland, Amsterdam, 1988, pp. 133–141. MR 922107, DOI 10.1016/S0049-237X(09)70655-X
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, DOI 10.2307/2586785
Joseph S. Miller and André Nies, Randomness and computability: open questions, Bull. Symbolic Logic 12 (2006), no. 3, 390–410. MR 2248590, DOI 10.2178/bsl/1154698740
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, Non-cupping and randomness, Proc. Amer. Math. Soc. 135 (2007), no. 3, 837–844. MR 2262880, DOI 10.1090/S0002-9939-06-08540-6
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
David B. Posner and Robert W. Robinson, Degrees joining to ${\bf 0}^{\prime }$, J. Symbolic Logic 46 (1981), no. 4, 714–722. MR 641485, DOI 10.2307/2273221
Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
Stephen G. Simpson, Almost everywhere domination and superhighness, MLQ Math. Log. Q. 53 (2007), no. 4-5, 462–482. MR 2351944, DOI 10.1002/malq.200710012
Theodore A. Slaman and John R. Steel, Complementation in the Turing degrees, J. Symbolic Logic 54 (1989), no. 1, 160–176. MR 987329, DOI 10.2307/2275022
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.