Low-like basis theorems for Ramsey's theorem for pairs in first-order arithmetic

Read full text
Authors: Hiroyuki Ikari, Keita Yokoyama
Cited by: 0

Abstract

We construct an $\ll^2$-solution (also known as a weakly low solution) to ${\mathrm{D}^2}$ within ${\mathrm{B}Σ^0_{3}}$ and prove the $\ll^2$-basis theorem for $\mathrm{RT}^2$ over ${\mathrm{B}Σ^0_{3}}$. The $\ll^2$-basis theorem is a variant of the low basis theorem, which has recently received focus in the context of the first-order part of Ramsey type theorems. For the construction, we use Mathias forcing in an effectively coded $ω$-model of $\mathsf{WKL_0}$ to ensure sufficient computability under the system with weaker induction. Using a similar method, we also show the $\ll^2$-basis theorem for $\mathrm{RT}^2_2$ and $\mathrm{EM}_{

Fields of Study & Subjects

Computability Logic AI Algorithms Advanced Topology and Set Theory Limits and Structures in Graph Theory

Publication details

Journal / source
arXiv (Cornell University)
Publication date
12 January 2026
Document type
Preprint