Ramsey’s theorem for singletons and strong computable reducibility
Damir D. Dzhafarov, Ludovic Patey, Reed Solomon, Linda Westrick · Proceedings of the American Mathematical Society · 2016
We answer a question posed by Hirschfeldt and Jockusch by showing that whenever k > ℓ k > \ell , Ramsey’s theorem for singletons and k k -colorings, R T k 1 \mathsf {RT}^1_k , is not strongly computably reducible to the stable Ramsey’s theorem for ℓ \ell -colorings, S R T ℓ 2 \mathsf {SRT}^2_\ell . Our proof actually establishes the following considerably stronger fact: given k > ℓ k > \ell , there is a coloring c : ω → k c : \omega \to k such that for every stable coloring d : [ ω ] 2 → ℓ d : [\omega ]^2 \to \ell (computable from c c or not), there is an infinite homogeneous set H H for d d that computes no infinite homogeneous set for c c . This also answers a separate question of Dzhafarov, as it follows that the cohesive principle, C O H