On the strength of Ramsey's theorem for pairs (Q2732267)

The authors use computability theory and proof theory to analyze various forms of Ramsey's theorem, obtaining especially interesting results about Ramsey's theorem for pairs. This work is closely related to earlier work of \textit{C.~Jockusch} [J. Symb. Log. 37, 268-280 (1972; Zbl 0262.02042)] and \textit{D.~Seetapun} and \textit{T.~Slaman} [Notre Dame J. Formal Logic 36, 570-582 (1995; Zbl 0843.03034)]. A forcing argument similar to one of \textit{C.~Jockusch} and \textit{F.~Stephan} [Math. Log. Q. 39, 515-530 (1993; Zbl 0799.03048)] proves that for any \(n \geq 2\) and any computable \(k\)-coloring of the \(n\)-element sets of natural numbers, there is an infinite homogeneous set \(X\), with \(X^{\prime \prime} \leq_{\text T} 0^{(n)}\). In particular, every computable \(k\)-coloring of pairs has a low\(_2\) homogeneous set. Additional forcing arguments show that RCA\(_0+\)I\(\Sigma_2 +\)RT\(_2^2\) is \(\Pi^1_1\)-conservative over RCA\(_0+\)I\(\Sigma_2\), leading to a proof that RT\(^2_{<\infty}\) is strictly stronger than RT\(^2_2\) over RCA\(_0\). After an analysis of the strength of statements concerning stable colorings and cohesive sets, the article concludes with a list of open questions and a comprehensive bibliography.