pith. sign in

arxiv: 1601.00050 · v4 · pith:I4K4NYB3new · submitted 2016-01-01 · 🧮 math.LO

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

classification 🧮 math.LO
keywords mathsfcolorsramseytheorempairsproof-theoreticsigmastrength
0
0 comments X
read the original abstract

Ramsey's theorem for $n$-tuples and $k$-colors ($\mathsf{RT}^n_k$) 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^0_1$ consequences, and show that $\mathsf{RT}^2_2$ is $\Pi^0_3$ conservative over $\mathsf{I}\Sigma^0_1$. This strengthens the proof of Chong, Slaman and Yang that $\mathsf{RT}^2_2$ does not imply $\mathsf{I}\Sigma^0_2$, 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^0_3$-conservation theorems.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.