Ramsey’s theorem for singletons and strong computable reducibility

Abstract:

We answer a question posed by Hirschfeldt and Jockusch by showing that whenever $k > \ell$, Ramsey’s theorem for singletons and $k$-colorings, $\mathsf {RT}^1_k$, is not strongly computably reducible to the stable Ramsey’s theorem for $\ell$-colorings, $\mathsf {SRT}^2_\ell$. Our proof actually establishes the following considerably stronger fact: given $k > \ell$, there is a coloring $c : \omega \to k$ such that for every stable coloring $d : [\omega ]^2 \to \ell$ (computable from $c$ or not), there is an infinite homogeneous set $H$ for $d$ that computes no infinite homogeneous set for $c$. This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, $\mathsf {COH}$, is not strongly computably reducible to the stable Ramsey’s theorem for all colorings, $\mathsf {SRT}^2_{<\infty }$. The latter is the strongest partial result to date in the direction of giving a negative answer to the longstanding open question of whether $\mathsf {COH}$ is implied by the stable Ramsey’s theorem in $\omega$-models of $\mathsf {RCA}_0$.