The reverse mathematics of bounded Ramsey's theorem for pairs

2025/09/03 by QUENTIN LE HOUÉROU, Houérou, Quentin Le, LUDOVIC PATEY +1 · 1 citation
#03B30 #03D80 (Secondary) #03F30 (Primary) 05D10 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2509.03688

Abstract

In this article, we study a degenerate version of Ramsey's theorem for pairs and two colors (RT²₂), in which the homogeneous sets for color 1 are of bounded size. By RT²₂, it follows that every such coloring admits an infinite homogeneous set for color 0. This statement, called BRT²₂, is known to be computably true, that is, every computable instance admits a computable solution, but the known proofs use Σ⁰₂-induction (IΣ₂⁰). We prove that BRT²₂ follows from the Erdős-Moser theorem but not from the Ascending Descending sequence principle, and that its computably true version is equivalent to IΣ₂⁰ over RCA₀.

Citations

• Conservation of Ramsey's theorem for pairs and well-foundedness
• Conservation theorems for the Cohesiveness Principle
• An isomorphism theorem for models of Weak König's Lemma without primitive recursion
• Very weak fragments of weak Kőnig's lemma
• Partial orders and immunity in reverse mathematics
• Separating principles below Ramsey's Theorem for Pairs
• Reverse Mathematics and Recursive Graph Theory

Cited by

• REVERSE MATHEMATICS AND DIMENSION OF POSETS
• Ramsey-like theorems for separable permutations

Related

• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Coloring the rationals in reverse mathematics
• Computable Ramsey's Theorem for Pairs Needs Infinitely Many Pi-0-2 Sets
• Somewhere over the rainbow Ramsey theorem for pairs
• A packed Ramsey's theorem and computability theory