On the Strength of Ramsey's Theorem for Pairs

Cholak, Peter A. ; Jockusch, Carl G. ; Slaman, Theodore A.

J. Symbolic Logic, Tome 66 (2001) no. 1, p. 1-55 / Harvested from Project Euclid

Résumé

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT$^n_k$ denote Ramsey's theorem for k-colorings of n-element sets, and let RT$^n_{<\infty}$ denote ($\forall k)RT^n_k$. Our main result on computability is: For any n $\geq$ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' $\leq_T 0^{(n)}$. Let $I\Sigma_n$ and $B\Sigma_n$ denote the $\Sigma_n$ induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low$_2$) to models of arithmetic enables us to show that $RCA_0 + I\Sigma_2 + RT^2_2$ is conservative over $RCA_0 + I\Sigma_2$ for $\Pi^1_1$ statements and that $RCA_0 + I\Sigma_3 + RT^2_{<\infty}$, is $\Pi^1_1$-conservative over $RCA_0 + I\Sigma_3$. It follows that $RCA_0 + RT^2_2$ does not imply $B\Sigma_3$. In contrast, J. Hirst showed that $RCA_0 + RT^2_{<\infty}$ does imply $B\Sigma_3$, and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{<\infty}$ is strictly stronger than $RT^2_2$ over $RCA_0$.

Détail

Publié le : 2001-03-14
Classification:  Ramsey's Theorem,  Conservation,  Reverse Mathematics,  Recursion Theory,  Computability Theory,  03F35,  03C62,  03D30,  03D80