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

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

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