The cohesive and stable Ramsey theorems and proof size over a weak base theory

arXiv:2604.01808 · math.LO · Submitted 2026-04-02 · Read on arXiv

math.LO

Submitted: 2026-04-02

Updated: 2026-10-28

Comments: 23 pages. Remark 3.5 corrected, new Remark 4.9 added

License: http://creativecommons.org/licenses/by/4.0/

The gist: We show that over the weak base theory RCA 0*, cohesive Ramsey's theorem for pairs CRT 2 2 implies exponential closure of the definable cut I 0 1…

Terminology

Abstract

We show that over the weak base theory RCA 0*, cohesive Ramsey's theorem for pairs CRT 2 2 implies exponential closure of the definable cut I 0 1, which is the intersection of all Σ 0 1-definable cuts. Consequences include non-elementary proof speedup of RCA 0* + CRT 2 2 over RCA 0* for Π 1 sentences and the unprovability of CRT 2 2 in RCA 0* + CAC. On the other hand, we show that RCA 0* + SRT 2 2, where SRT 2 2 is stable Ramsey's theorem for pairs, is polynomially simulated by RCA 0* with respect to proofs of Π 0 3 sentences. Nevertheless, SRT 2 2 also implies a nontrivial property of I 0 1, specifically closure under functions of quasipolynomial growth rate.

Sources

Related papers