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

by Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjorn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman



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: 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