The Strength of Some Combinatorial Principles Related to
Ramsey's Theorem for Pairs
Status: published in Chong, Feng, Slaman, Woodin, and Yang (eds.),
Computational
Prospects
of Infinity, Part II: Presented Talks, Lecture Notes Series,
Institute for
Mathematical
Sciences, National University of Singapore, Vol. 15, World Scientific
2008, 143 - 161.
Availability: published
version and preprint
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
Δ02 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