A non-speedup result for the chain-antichain principle over a weak base theory

Read full text
Authors: Katarzyna W. Kowalik
Cited by: 0

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