THE STRENGTH OF SOME COMBINATORIAL PRINCIPLES RELATED TO RAMSEY'S THEOREM FOR PAIRS
Denis R. Hirschfeldt, Carl G. Jockusch, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman · Lecture notes series, Institute For Mathematical Sciences · 2008
Abstract. We study the reverse mathematics and computability-the-oretic 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. 1.