A non speed-up result for the chain-antichain principle over a weak base theory
The chain-antichain principle (CAC), a well-known consequence of Ramsey’s Theorem for pairs and two colours, says that for every partial order on ℕ there exists an infinite chain or antichain with respect to this order. We study the strength of this principle over the weak base theory RCA0*, which is obtained from RCA0 by replacing the Σ10-induction scheme with Δ10-induction.
It was shown by Patey and Yokoyama in [3] that RT22 is Π30-conservative over RCA0 and from [4] it follows that RT22 is also Π30-conservative over RCA0* (cf. [1]). The conservativity results lead to the question whether RT22 has significantly shorter proofs for Π30-sentences. The answer depends on the choice of the base theory: it was proved in [2] that RT22 can be polynomially simulated by RCA0 for Π30-sentences but it has non-elementary speed-up over RCA0* for Σ10-sentences.
The speed-up result was obtained by the use of the exponential lower bound for the finite version of RT22. However, it follows from Dilworth’s theorem that the upper bound for the finite version of CAC is polynomial. This suggests that CAC, despite being a relatively strong consequence of RT22, might not have an analogous speed-up over RCA0*. We confirm this conjecture by constructing a two-step forcing interpretation of RCA0*+CAC in RCA0*.
References
- [1]
- Leszek A. Kołodziejczyk, Katarzyna W. Kowalik, Keita Yokoyama, How strong is Ramsey’s theorem if infinity can be weak? Submitted. Available at arXiv:2011.02550.
- [2]
- Leszek A. Kołodziejczyk, Tin Lok Wong, Keita Yokoyama, Ramsey’s theorem for pairs, collection, and proof size. Submitted. Available at arXiv:2005.06854.
- [3]
- Ludovic Patey, Keita Yokoyama, The proof-theoretic strength of Ramsey’s theorem for pairs and two colors, Advances in Mathematics, vol. 330 (2018), pp. 1034–1070.
- [4]
- Keita Yokoyama, On the strength of Ramsey’s theorem without Σ1-induction, Mathematical Logic Quarterly, vol. 59 (2013), no. 1-2, pp. 108–111.
This document was translated from LATEX by HEVEA.