Cone avoiding closed sets

Liu, Lu

doi:10.1090/S0002-9947-2014-06049-2

Cone avoiding closed sets
HTML articles powered by AMS MathViewer

by Lu Liu PDF

Trans. Amer. Math. Soc. 367 (2015), 1609-1630 Request permission

Abstract:

We prove that for an arbitrary subtree $T$ of $2^{<\omega }$ with each element extendable to a path, a given countable class $\mathcal {M}$ closed under disjoint union, and any set $A$, if none of the members of $\mathcal {M}$ strongly $k$-enumerate $T$ for any $k$, then there exists an infinite set contained in either $A$ or $\bar {A}$ such that for every $C\in \mathcal {M}$, $C\oplus G$ also does not strongly $k$-enumerate $T$. We give applications of this result, which include: (1) $\mathsf {RT_2^2}$ doesn’t imply $\mathsf {WWKL_0}$; (2) [Ambos-Spies et al., 2004] $\mathsf {DNR}$ is strictly weaker than $\mathsf {WWKL_0}$; (3) [Kjos-Hanssen, 2009] for any Martin-Löf random set $A$, either $A$ or $\bar {A}$ contains an infinite subset that does not compute any Martin-Löf random set; etc. We also discuss further generalizations of this result.

References

Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman, Comparing DNR and WWKL, J. Symbolic Logic 69 (2004), no. 4, 1089–1104. MR 2135656, DOI 10.2178/jsl/1102022212
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpre, Andrej Muchnik, Frank Stephan, and Leen Torenvliet, Enumerations of the Kolmogorov function, J. Symbolic Logic 71 (2006), no. 2, 501–528. MR 2225891, DOI 10.2178/jsl/1146620156
Peter A. Cholak, Carl G. Jockusch Jr., and Theodore A. Slaman, Corrigendum to: “On the strength of Ramsey’s theorem for pairs” [MR1825173], J. Symbolic Logic 74 (2009), no. 4, 1438–1439. MR 2583829, DOI 10.2178/jsl/1254748700
Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55. MR 1825173, DOI 10.2307/2694910
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
Damir D. Dzhafarov and Carl G. Jockusch Jr., Ramsey’s theorem and cone avoidance, J. Symbolic Logic 74 (2009), no. 2, 557–578. MR 2518811, DOI 10.2178/jsl/1243948327
Harvey Friedman, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974) Canad. Math. Congress, Montreal, Que., 1975, pp. 235–242. MR 0429508
Harvey Friedman, Systems of second order arithmetic with restricted induction, i, ii, Journal of Symbolic Logic 41 (1976), no. 2, 557–559.
Noam Greenberg and Joseph S. Miller, Diagonally non-recursive functions and effective Hausdorff dimension, Bull. Lond. Math. Soc. 43 (2011), no. 4, 636–654. MR 2820150, DOI 10.1112/blms/bdr003
D. R. Hirschfeldt, C. G. Jockusch Jr., B. Kjos-Hanssen, S. Lempp, and T. A. Slaman, The strength of some combinatorial principles related to Ramsey’s theorem for pairs, Computational Prospects of Infinity: Presented talks 14 (2008), 143–161.
Jiayi Liu, ${\mathsf {RT}}^2_2$ does not imply ${\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609–620. MR 2963024, DOI 10.2178/jsl/1333566640
Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
Bjørn Kjos-Hanssen, Infinite subsets of random sets of integers, Math. Res. Lett. 16 (2009), no. 1, 103–110. MR 2480564, DOI 10.4310/MRL.2009.v16.n1.a10
Bjørn Kjos-Hanssen, A strong law of computationally weak subsets, J. Math. Log. 11 (2011), no. 1, 1–10. MR 2833148, DOI 10.1142/S0219061311000980
Masahiro Kumabe and Andrew E. M. Lewis, A fixed-point-free minimal degree, J. Lond. Math. Soc. (2) 80 (2009), no. 3, 785–797. MR 2559129, DOI 10.1112/jlms/jdp049
Jack H. Lutz, Gales and the constructive dimension of individual sequences, Automata, languages and programming (Geneva, 2000) Lecture Notes in Comput. Sci., vol. 1853, Springer, Berlin, 2000, pp. 902–913. MR 1795945, DOI 10.1007/3-540-45022-X_{7}6
Elvira Mayordomo, A Kolmogorov complexity characterization of constructive Hausdorff dimension, Inform. Process. Lett. 84 (2002), no. 1, 1–3. MR 1926330, DOI 10.1016/S0020-0190(02)00343-5
Joseph S. Miller, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Adv. Math. 226 (2011), no. 1, 373–384. MR 2735764, DOI 10.1016/j.aim.2010.06.024
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
F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. (2) 30 (1929), no. 4, 264–286. MR 1576401, DOI 10.1112/plms/s2-30.1.264
B. Ya. Ryabko, Coding of combinatorial sources and Hausdorff dimension, Dokl. Akad. Nauk SSSR 277 (1984), no. 5, 1066–1070 (Russian). MR 759967
David Seetapun and Theodore A. Slaman, On the strength of Ramsey’s theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570–582. Special Issue: Models of arithmetic. MR 1368468, DOI 10.1305/ndjfl/1040136917
Stephen G. Simpson, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993, DOI 10.1007/978-3-642-59971-2