The proof-theoretic strength of Ramsey's theorem for pairs and two colors

Abstract

Ramsey's theorem for $n$-tuples and $k$-colors (${\mathsf{RT}}_k^n$) asserts that every k-coloring of $[\mathbb{N}{]}^n$ admits an infinite monochromatic subset. We study the proof-theoretic strength of Ramsey's theorem for pairs and two colors, namely, the set of its ${\Pi }_1^0$ consequences, and show that ${\mathsf{RT}}_2^2$ is ${\Pi }_3^0$ conservative over $\mathsf{I}{\Sigma }_1^0$. This strengthens the proof of Chong, Slaman and Yang that ${\mathsf{RT}}_2^2$ does not imply $\mathsf{I}{\Sigma }_2^0$, and shows that ${\mathsf{RT}}_2^2$ is finitistically reducible, in the sense of Simpson's partial realization of Hilbert's Program. Moreover, we develop general tools to simplify the proofs of ${\Pi }_3^0$-conservation theorems.

32 pages

Cited by in corpus (1)

• Computational reverse mathematics and foundational analysis