The Strength of Some Combinatorial Principles Related to
Ramsey's Theorem for Pairs
Status: to appear in the proceedings of the Program on Computational
Prospects of Infinity, Singapore 2005.
Availability: PostScript, DVI, and PDF
Abstract. We study the reverse mathematics and
computability-theoretic strength of (stable) Ramsey's Theorem for
pairs and the related principles COH and DNR. We show that
SRT22 implies DNR over RCA0 but COH
does not, and answer a question of Mileti by showing that every
computable stable 2-coloring of pairs has an incomplete
Delta02 infinite homogeneous set. We also give
some extensions of the latter result, and relate it to potential
approaches to showing that SRT22 does not imply
RT22.
drh@math.uchicago.edu