The cohesive and stable Ramsey theorems and proof size over a weak base theory
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.01808
curl -X POST /api/v1/records/arxiv/2604.01808/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.01808/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'