The strength of Ramsey's theorem for pairs and arbitrarily many colors

2017/11/23 by Theodore A. Slaman, Slaman, Theodore A., Keita Yokoyama +1 · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Advanced Topology and Set Theory #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1711.08704

Abstract

In this paper, we show that RT²+WKL₀ is a Π¹₁-conservative extension of BΣ⁰₃.

Cited by

• Ordinal Analysis of Well-Ordering Principles, Well Quasi-Orders Closure Properties, and Σ_n-Collection Schema

Related

• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Conservation of Ramsey's theorem for pairs and well-foundedness
• Π⁰₄ conservation of Ramsey's theorem for pairs
• The reverse mathematics of bounded Ramsey's theorem for pairs
• Erdos-Moser and ISigma₂