What type of study is this?

This is a Quantitative Study study.

October 5, 2025Open Access

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

Key Points

The theory WKL_0^* + CAC is polynomially simulated by RCA_0^* for all Π^0_3 formulas, showcasing an important relationship.
Forcing interpretations and a restricted definable ultrapower construction are integral to the proof methodology used.
This result significantly contrasts with previous findings where RCA_0^* + RT^2_2 exhibited non-elementary speedup over RCA_0^*.
This highlights the complexities within mathematical logic and the implications of simulation properties in weak theories.

Abstract

We show that the theory WKL^*₀+CAC is polynomially simulated by RCA₀^* with respect to Π⁰₃ 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 CAC. Our result sharply contrasts with the previously known fact that RCA₀^*+RT²₂ has non-elementary speedup over RCA₀^*.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

Katarzyna W. Kowalik (Tue,) studied this question.

synapsesocial.com/papers/68e24e6fd6d66a53c2473ed1 https://doi.org/https://doi.org/10.48550/arxiv.2510.00323

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Mark Helpful

Bookmark

Relay

View Full Paper