The metamathematics of Stable Ramsey’s Theorem for Pairs

DOI10.1090/S0894-0347-2014-00789-XzbMath1341.03015OpenAlexW2102358420MaRDI QIDQ3190948

Yue Yang, Theodore A. Slaman, Chi Tat Chong

Publication date: 19 September 2014

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0894-0347-2014-00789-x

Mathematics Subject Classification ID

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

Related Items

An inside/outside Ramsey theorem and recursion theory ⋮ Reduction games, provability and compactness ⋮ Inductive inference and reverse mathematics ⋮ The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ On principles between ∑1- and ∑2-induction, and monotone enumerations ⋮ Computable Reductions and Reverse Mathematics ⋮ NONSTANDARD MODELS IN RECURSION THEORY AND REVERSE MATHEMATICS ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ Extracting randomness within a subset is hard ⋮ On the strength of Ramsey's theorem for trees ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK? ⋮ The Paris-Harrington principle and second-order arithmetic -- bridging the finite and infinite Ramsey theorem ⋮ Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE ⋮ Some Questions in Computable Mathematics ⋮ STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES ⋮ THE STRENGTH OF THE TREE THEOREM FOR PAIRS IN REVERSE MATHEMATICS ⋮ Some logically weak Ramseyan theorems ⋮ Degrees bounding principles and universal instances in reverse mathematics ⋮ On the logical strengths of partial solutions to mathematical problems ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ A weak variant of Hindman's theorem stronger than Hilbert's theorem ⋮ The inductive strength of Ramsey's theorem for pairs ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ New bounds on the strength of some restrictions of Hindman's theorem ⋮ COMPARING THE STRENGTH OF DIAGONALLY NONRECURSIVE FUNCTIONS IN THE ABSENCE OF INDUCTION ⋮ On uniform relationships between combinatorial problems ⋮ \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models ⋮ The atomic model theorem and type omitting ⋮ Reverse mathematics and colorings of hypergraphs ⋮ Pigeons do not jump high ⋮ Cohesive avoidance and strong reductions ⋮ 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

• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• A Δ₂⁰ set with no infinite low subset in either it or its complement
• RT₂² does not imply WKL₀
• On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics
• Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
• Σ_{𝑛}-bounding and Δ_{𝑛}-induction
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory
• Recursive Predicates and Quantifiers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item