## Cohesive avoidance and strong reductions

HTML articles powered by AMS MathViewer

- by Damir D. Dzhafarov PDF
- Proc. Amer. Math. Soc.
**143**(2015), 869-876 Request permission

## Abstract:

An open question in reverse mathematics is whether the cohesive principle, $\mathsf {COH}$, is implied by the stable form of Ramsey’s theorem for pairs, $\mathsf {SRT}^2_2$, in $\omega$-models of $\mathsf {RCA}_0$. One typical way of establishing this implication would be to show that for every sequence $\vec {R}$ of subsets of $\omega$, there is a set $A$ that is $\Delta ^0_2$ in $\vec {R}$ such that every infinite subset of $A$ or $\overline {A}$ computes an $\vec {R}$-cohesive set. In this article, this is shown to be false, even under far less stringent assumptions: for all natural numbers $n \geq 2$ and $m < 2^n$, there is a sequence $\vec {R} = \langle {R_0,\ldots ,R_{n-1}}\rangle$ of subsets of $\omega$ such that for any partition $A_0,\ldots ,A_{m-1}$ of $\omega$ hyperarithmetical in $\vec {R}$, there is an infinite subset of some $A_j$ that computes no set cohesive for $\vec {R}$. This complements a number of previous results in computability theory on the computational feebleness of infinite sets of numbers with prescribed combinatorial properties. The proof is a forcing argument using an adaptation of the method of Seetapun showing that every finite coloring of pairs of integers has an infinite homogeneous set not computing a given non-computable set.## References

- 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 - C. T. Chong, Steffen Lempp, and Yue Yang,
*On the role of the collection principle for $\Sigma ^0_2$-formulas in second-order reverse mathematics*, Proc. Amer. Math. Soc.**138**(2010), no. 3, 1093–1100. MR**2566574**, DOI 10.1090/S0002-9939-09-10115-6 - C. T. Chong, Theodore A. Slaman, and Yue Yang,
*The metamathematics of stable Ramsey’s theorem for pairs*, J. Amer. Math. Soc.**27**(2014), no. 3, 863–892. MR**3194495**, DOI 10.1090/S0894-0347-2014-00789-X - S. B. Cooper,
*Jump equivalence of the $\Delta ^{0}_{2}$ hyperhyperimmune sets*, J. Symbolic Logic**37**(1972), 598–600. MR**360240**, DOI 10.2307/2272750 - François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer,
*On uniform relationships between combinatorial problems*. To appear. - 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 - Damir D. Dzhafarov and Carl Mummert,
*On the strength of the finite intersection principle*, Israel J. Math.**196**(2013), no. 1, 345–361. MR**3096595**, DOI 10.1007/s11856-012-0150-9 - D. R. Hirschfeldt and C. G. Jockusch, Jr.,
*On notions of computability theoretic reduction between $\Pi ^1_2$ principles*, to appear. - Denis R. Hirschfeldt,
*Slicing the truth: On the computability theoretic and reverse mathematical analysis of combinatorial principles*. In Asian Initiative for Infinity: AII Graduate Summer School, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap. World Sci. Publ., Hackensack, NJ, to appear. - Denis R. Hirschfeldt and Richard A. Shore,
*Combinatorial principles weaker than Ramsey’s theorem for pairs*, J. Symbolic Logic**72**(2007), no. 1, 171–206. MR**2298478**, DOI 10.2178/jsl/1174668391 - Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman,
*The atomic model theorem and type omitting*, Trans. Amer. Math. Soc.**361**(2009), no. 11, 5805–5837. MR**2529915**, DOI 10.1090/S0002-9947-09-04847-8 - Tamara Hummel and Carl G. Jockusch Jr.,
*Generalized cohesiveness*, J. Symbolic Logic**64**(1999), no. 2, 489–516. MR**1777768**, DOI 10.2307/2586482 - Carl G. Jockusch Jr.,
*Upward closure and cohesive degrees*, Israel J. Math.**15**(1973), 332–335. MR**347573**, DOI 10.1007/BF02787575 - Carl Jockusch and Frank Stephan,
*A cohesive set which is not high*, Math. Logic Quart.**39**(1993), no. 4, 515–530. MR**1270396**, DOI 10.1002/malq.19930390153 - 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 - Joseph Roy Mileti,
*Partition theorems and computability theory*, ProQuest LLC, Ann Arbor, MI, 2004. Thesis (Ph.D.)–University of Illinois at Urbana-Champaign. MR**2706695** - Gerald E. Sacks,
*Higher recursion theory*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR**1080970**, DOI 10.1007/BFb0086109 - 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 - Richard A. Shore,
*Rigidity and biinterpretability in the hyperdegrees*, 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. 299–312. MR**2449471**, DOI 10.1142/9789812796554_{0}016 - Stephen G. Simpson,
*Subsystems of second order arithmetic*, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR**2517689**, DOI 10.1017/CBO9780511581007 - Robert I. Soare,
*Sets with no subset of higher degree*, J. Symbolic Logic**34**(1969), 53–56. MR**263627**, DOI 10.2307/2270981 - Robert I. Soare,
*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**, DOI 10.1007/978-3-662-02460-7

## Additional Information

**Damir D. Dzhafarov**- Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720
- MR Author ID: 781680
- ORCID: 0000-0003-4921-7561
- Email: damir@math.berkeley.edu
- Received by editor(s): March 18, 2013
- Received by editor(s) in revised form: May 15, 2013
- Published electronically: October 23, 2014
- Additional Notes: The author was partially supported by an NSF Postdoctoral Fellowship and by the John Templeton Foundation
- Communicated by: Mirna Dz̆amonja
- © Copyright 2014
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc.
**143**(2015), 869-876 - MSC (2010): Primary 03D80, 03F35, 05D05, 05D10
- DOI: https://doi.org/10.1090/S0002-9939-2014-12261-1
- MathSciNet review: 3283673