| Autor: |
FernÁndez-Duque, David, Joosten, Joost J, Pakhomov, Fedor, Papafilippou, Konstantinos, Weierman, Andreas |
| Předmět: |
|
| Zdroj: |
Journal of Logic & Computation; Dec2022, Vol. 32 Issue 8, p1558-1584, 27p |
| Abstrakt: |
Japaridze's provability logic |${\operatorname {GLP}}$| has one modality |$[n]$| for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano arithmetic (|${\operatorname {PA}}$|) and related theories. Among other benefits, this analysis yields the so-called Every Worm Dies (|${\operatorname {EWD}}$|) principle, a natural combinatorial statement independent of |${\operatorname {PA}}$|. Recently, Beklemishev and Pakhomov have studied notions of provability corresponding to transfinite modalities in |${\operatorname {GLP}}$|. We show that indeed the natural transfinite extension of |${\operatorname {GLP}}$| is sound for this interpretation and yields independent combinatorial principles for the second-order theory |${\operatorname {ACA}}$| of arithmetical comprehension with full induction. We also provide restricted versions of |${\operatorname {EWD}}$| related to the fragments |${\operatorname {I\varSigma }}_n$| of PA. In order to prove the latter, we show that standard Hardy functions majorize their variants based on tree ordinals. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
