THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS
The Journal of Symbolic Logic · 18.06.2026 · 1-26
DOI: 10.1017/jsl.2026.10226 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Journal of Symbolic Logic, online erschienen am 18.06.2026. Verfasst von QUENTIN LE HOUÉROU und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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 ^0_2$ sans serif upper I normal upper Sigma 2 Superscript 0 over RCA 0 ${\mathsf {RCA}}_0$ sans serif upper R upper C upper A 0 .
Zitieren
APA
HOUÉROU, Q. L., & PATEY, L. (2026). THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS. The Journal of Symbolic Logic, 1-26. https://doi.org/10.1017/jsl.2026.10226
Vancouver
HOUÉROU QL, PATEY L. THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS. The Journal of Symbolic Logic. 2026:1-26. doi:10.1017/jsl.2026.10226
BibTeX
@article{HOUROU2026,
author = {HOUÉROU, QUENTIN LE and PATEY, LUDOVIC},
title = {THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS},
journal = {The Journal of Symbolic Logic},
year = {2026},
pages = {1--26},
doi = {10.1017/jsl.2026.10226}
}
EUVIMED