The reverse mathematics of bounded Ramsey's theorem for pairs

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 $Σ^0_2$-induction ($\mathsf{I}Σ_2^0$). We prove that $\mathsf{BRT}^2_2$ follows from the Erdős-Moser theorem but not from the Ascending Descending sequence principle, and that its computably true version is equivalent to $\mathsf{I}Σ_2^0$ over $\mathsf{RCA}_0$.

Publication Details

Journal
ArXiv.org
Published
2025-09-03
Primary Topic
Geochemistry and Geologic Mapping
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

The reverse mathematics of bounded Ramsey's theorem for pairs

ArXiv.org
Geochemistry and Geologic Mapping
article

The reverse mathematics of bounded Ramsey's theorem for pairs

article en

Abstract

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 $Σ^0_2$-induction ($\mathsf{I}Σ_2^0$). We prove that $\mathsf{BRT}^2_2$ follows from the Erdős-Moser theorem but not from the Ascending Descending sequence principle, and that its computably true version is equivalent to $\mathsf{I}Σ_2^0$ over $\mathsf{RCA}_0$.

ArXiv.org
Openalex Percentile: Top 48%
Geochemistry and Geologic Mapping
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

The reverse mathematics of bounded Ramsey's theorem for pairs · ArXiv.org (2025) | TGRS Research Map | TGRS