Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.01808 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909029133975552 |
|---|---|
| author | Kołodziejczyk, Leszek Aleksander Sun, Mengzhou |
| author_facet | Kołodziejczyk, Leszek Aleksander Sun, Mengzhou |
| contents | We show that over the weak base theory $\mathrm{RCA}_0^*$, cohesive Ramsey's theorem for pairs $\mathrm{CRT}^2_2$ implies exponential closure of the definable cut $\mathrm{I}^0_1$, which is the intersection of all $Σ^0_1$-definable cuts. Consequences include non-elementary proof speedup of $\mathrm{RCA}_0^* + \mathrm{CRT}^2_2$ over $\mathrm{RCA}_0^*$ for $Π_1$ sentences and the unprovability of $\mathrm{CRT}^2_2$ in $\mathrm{RCA}_0^* + \mathrm{CAC}$.
On the other hand, we show that $\mathrm{RCA}_0^* + \mathrm{SRT}^2_2$, where $\mathrm{SRT}^2_2$ is stable Ramsey's theorem for pairs, is polynomially simulated by $\mathrm{RCA}_0^*$ with respect to proofs of $\forall Π^0_3$ sentences. Nevertheless, $\mathrm{SRT}^2_2$ also implies a nontrivial property of $\mathrm{I}^0_1$, specifically closure under functions of quasipolynomial growth rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_01808 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The cohesive and stable Ramsey theorems and proof size over a weak base theory Kołodziejczyk, Leszek Aleksander Sun, Mengzhou Logic 03B30, 03F20 (Primary) 03F25, 03F35, 03H15, 05D10 (Secondary) We show that over the weak base theory $\mathrm{RCA}_0^*$, cohesive Ramsey's theorem for pairs $\mathrm{CRT}^2_2$ implies exponential closure of the definable cut $\mathrm{I}^0_1$, which is the intersection of all $Σ^0_1$-definable cuts. Consequences include non-elementary proof speedup of $\mathrm{RCA}_0^* + \mathrm{CRT}^2_2$ over $\mathrm{RCA}_0^*$ for $Π_1$ sentences and the unprovability of $\mathrm{CRT}^2_2$ in $\mathrm{RCA}_0^* + \mathrm{CAC}$. On the other hand, we show that $\mathrm{RCA}_0^* + \mathrm{SRT}^2_2$, where $\mathrm{SRT}^2_2$ is stable Ramsey's theorem for pairs, is polynomially simulated by $\mathrm{RCA}_0^*$ with respect to proofs of $\forall Π^0_3$ sentences. Nevertheless, $\mathrm{SRT}^2_2$ also implies a nontrivial property of $\mathrm{I}^0_1$, specifically closure under functions of quasipolynomial growth rate. |
| title | The cohesive and stable Ramsey theorems and proof size over a weak base theory |
| topic | Logic 03B30, 03F20 (Primary) 03F25, 03F35, 03H15, 05D10 (Secondary) |
| url | https://arxiv.org/abs/2604.01808 |