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

2016/01/01 by Ludovic Patey, Patey, Ludovic, Keita Yokoyama +1 · 4 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.1601.00050

openalex publication_date 2016/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Ramsey's theorem for n-tuples and k-colors (RTⁿ_k) asserts that every k-coloring of [ℕ]ⁿ 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 Π⁰₁ consequences, and show that RT²₂ is Π⁰₃ conservative over IΣ⁰₁. This strengthens the proof of Chong, Slaman and Yang that RT²₂ does not imply IΣ⁰₂, and shows that RT²₂ 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 Π⁰₃-conservation theorems.

Cited by

• Definability over \mathrm BΣ⁰₂-models
• Π⁰₄ conservation of a Carlson-Simpson lemma for 1-variable words
• Ramsey-like theorems and immunities
• Ramsey-like theorems for separable permutations

Related

• The strength of Ramsey's theorem for pairs and arbitrarily many colors
• Π⁰₄ conservation of Ramsey's theorem for pairs
• The reverse mathematics of bounded Ramsey's theorem for pairs
• Conservation of Ramsey's theorem for pairs and well-foundedness
• SRT22 does not imply RT22 in omega-models