## 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

## Additional Information

**Lu Liu**- Affiliation: Department of Mathematics, Central South University, ChangSha 410083, People’s Republic of China
- MR Author ID: 980145
- Email: g.jiayi.liu@gmail.com
- Received by editor(s): November 20, 2010
- Received by editor(s) in revised form: December 12, 2012
- Published electronically: November 4, 2014
- © Copyright 2014
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**367**(2015), 1609-1630 - MSC (2010): Primary 03B30; Secondary 03F35, 03C62, 68Q30, 03D32, 03D80, 28A78
- DOI: https://doi.org/10.1090/S0002-9947-2014-06049-2
- MathSciNet review: 3286494