EUVIMEDEUVIMED entdecken
Crossref

THE REVERSE MATHEMATICS OF BOUNDED RAMSEY’S THEOREM FOR PAIRS

QUENTIN LE HOUÉROU, LUDOVIC PATEY

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →