The inductive strength of Ramsey's theorem for pairs

DOI10.1016/j.aim.2016.11.036zbMath1423.03047OpenAlexW2565215485MaRDI QIDQ507201

Yue Yang, Theodore A. Slaman, Chi Tat Chong

Publication date: 3 February 2017

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2016.11.036

zbMATH Keywords

reverse mathematicsRamsey's theorem for pairs\(\mathrm{RCA}_0\)\(\operatorname{\Sigma}_2^0\)-boundingstable Ramsey's theorem for pairs

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Related Items (13)

The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ On principles between ∑1- and ∑2-induction, and monotone enumerations ⋮ Book review of: D. R. Hirschfeldt, Slicing the truth. On the computable and reverse mathematics of combinatorial principles ⋮ On the strength of Ramsey's theorem for trees ⋮ HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK? ⋮ Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs ⋮ Variations of statement, variations of strength. The case of the Rival-Sands theorems ⋮ (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE ⋮ Some Questions in Computable Mathematics ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS ⋮ The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma ⋮ In search of the first-order part of Ramsey's theorem for pairs

Cites Work

• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• The degree of a \(\Sigma_ n\) cut
• On the strength of Ramsey's theorem for pairs
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics
• Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
• Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
• Σ_{𝑛}-bounding and Δ_{𝑛}-induction
• Ramsey's theorem and recursion theory

This page was built for publication: The inductive strength of Ramsey's theorem for pairs