Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Cohesive avoidance and strong reductions

Author: Damir D. Dzhafarov
Journal: Proc. Amer. Math. Soc. 143 (2015), 869-876
MSC (2010): Primary 03D80, 03F35, 05D05, 05D10
Published electronically: October 23, 2014
MathSciNet review: 3283673
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D80, 03F35, 05D05, 05D10

Retrieve articles in all journals with MSC (2010): 03D80, 03F35, 05D05, 05D10

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

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
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.