A non-speedup result for the chain-antichain principle over a weak base theory
Abstract
We show that the theory $\mathsf{WKL}^*_0+\mathsf{CAC}$ is polynomially simulated by $\mathsf{RCA}_0^*$ with respect to $\forallΠ^0_3$ formulas. For the proof, we use the method of forcing interpretations and syntactically simulate a two-step model-theoretic argument, which involves construction of a restricted definable ultrapower, followed by a generic cut satisfying $\mathsf{CAC}$. Our result sharply contrasts with the previously known fact that $\mathsf{RCA}_0^*+\mathsf{RT}^2_2$ has non-elementary speedup over $\mathsf{RCA}_0^*$.
Fields of Study & Subjects
Black Holes and Theoretical Physics
Nonlinear Waves and Solitons
Cosmology and Gravitation Theories
Publication details
- Journal / source
- Transactions of the American Mathematical Society
- Publication date
- 9 May 2026
- Language
- EN