THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS

Abstract In this article, we study a degenerate version of Ramsey’s theorem for pairs and two colors ( RT 2 2 ${\mathsf {RT}}^2_2$ sans serif upper R upper T 2 squared ), in which the homogeneous sets for color 1 are of bounded size. By RT 2 2 ${\mathsf {RT}}^2_2$ sans serif upper R upper T 2 squared , it follows that every such coloring admits an infinite homogeneous set for color 0. This statement, called BRT 2 2 ${\mathsf {BRT}}^2_2$ sans serif upper B upper R upper T 2 squared , is known to be computably true, that is, every computable instance admits a computable solution, but the known proofs use Σ 2 0 $\Sigma ^0_2$ normal upper Sigma 2 Superscript 0 -induction ( I Σ 2 0 $\mathsf {I}\Sigma ^0_2$ sans serif upper I normal upper Sigma 2 Superscript 0 ). We prove that BRT 2 2 ${\mathsf {BRT}}^2_2$ sans serif upper B upper R upper T 2 squared 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 Σ 2 0 $\mathsf {I}\Sigma