The cohesive and stable Ramsey theorems and proof size over a weak base theory
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
- Conservation theorems for the Cohesiveness Principle
- A non-speedup result for the chain-antichain principle over a weak base theory
- Largeness notions and polytime translation for $\forall \Sigma^0_3$-consequences of $\mathsf{RT}^2_2$
- The finite cohesiveness principle
Related papers
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- Indiscernible Extraction in Theories with Bounded k-splitting
- Measuring the Complexity of Countable Presburger Models
- A non-trivially non-trivial automorphism at an inaccessible cardinal
- The Ordering Principle and Higher Dependent Choice