Arithmetical and Hyperarithmetical Worm Battles

0565843 - ÚI 2023 RIV GB eng J - Článek v odborném periodiku
Fernández-Duque, David - Joosten, J.J. - Pakhomov, F. - Papafilippou, K. - Weierman, A.
Arithmetical and Hyperarithmetical Worm Battles.
Journal of Logic and Computation. Roč. 32, č. 8 (2022), s. 1558-1584. ISSN 0955-792X. E-ISSN 1465-363X
Institucionální podpora: RVO:67985807
Klíčová slova: provability logics * independence results * ordinal analysis
Obor OECD: Pure mathematics
Impakt faktor: 0.7, rok: 2022
Způsob publikování: Omezený přístup
https://dx.doi.org/10.1093/logcom/exac067

Japaridze's provability logic GLP has one modality [n] for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano arithmetic (PA) and related theories. Among other benefits, this analysis yields the so called Every Worm Dies (EWD) principle, a natural combinatorial statement independent of PA. Recently, Beklemishev and Pakhomov have studied notions of provability corresponding to transfinite modalities in GLP. We show that indeed the natural transfinite extension of GLP is sound for this interpretation and yields independent combinatorial principles for the second-order theory ACA of arithmetical comprehension with full induction. We also provide restricted versions of EWD related to the fragments I Sigma(n) of PA. In order to prove the latter, we show that standard Hardy functions majorize their variants based on tree ordinals.
Trvalý link: https://hdl.handle.net/11104/0337335