The reverse mathematics of bounded Ramsey’s theorem for pairs
Published:
In this article, we study a degenerate version of Ramsey’s theorem for pairs and two colors (\( \mathsf{RT}^2_2 \)), in which the homogeneous sets for color \(1\) are of bounded size. By \( \mathsf{RT}^2_2 \), it follows that every such coloring admits an infinite homogeneous set for color 0. This statement, called \( \mathsf{BRT}^2_2 \), is known to be computably true, that is, every computable instance admits a computable solution, but the known proofs use \( \Sigma^0_2 \)-induction (\(\mathsf{I}\Sigma^0_2\)). We prove that \( \mathsf{BRT}^2_2 \) follows from the Erd\H{o}s-Moser theorem but not from the Ascending Descending sequence principle, and that its computably true version is equivalent to \(\mathsf{I}\Sigma^0_2\) over \( \mathsf{RCA}_0 \).
Recommended citation: Q. Le Houérou and L. Patey. "The reverse mathematics of bounded Ramsey's theorem for pairs." The Journal of Symbolic Logic. Published online 2026:1-26. doi:10.1017/jsl.2026.10226.
Download Paper