2016/02/14 by Dzhafarov, Damir D., Patey, Ludovic, Solomon, Reed +1
#FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1602.04481
We answer a question posed by Hirschfeldt and Jockusch by showing that whenever k > ℓ, Ramsey's theorem for singletons and k-colorings, RT1k, is not strongly computably reducible to the stable Ramsey's theorem for ℓ-colorings, SRT2_ℓ. Our proof actually establishes the following considerably stronger fact: given k > ℓ, there is a coloring c : ω→ k such that for every stable coloring d : [ω]2 → ℓ (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, COH, is not strongly computably reducible to the stable Ramsey's theorem for all colorings, SRT2_