Cohesive avoidance and strong reductions

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.