The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

Abstract

We study the reverse mathematics and computability-the\-o\-re\-tic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT${}_2^2$ implies DNR over RCA${}_0$ but COH does not, and answer a question of Mileti by showing that every computable stable $2$-coloring of pairs has an incomplete ${\Delta }_2^0$ infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT${}_2^2$ does not imply RT${}_2^2$.

Cited by in corpus (2)

• Somewhere over the rainbow Ramsey theorem for pairs
• Relationships between computability-theoretic properties of problems