This paper introduces three cut-free sequent calculi for RC₁, the strictly positive fragment of Gödel-Löb's provability logic. We establish cut admissibility for all three systems—G1RC1, G1K4⁺, and G1K4⁺—which differ in their treatment of modal rules for necessitation and diamond transitivity. The calculi operate on single formulas rather than multisets, answering an open question about non-nested proof systems for reflection calculi. We demonstrate that our systems are equivalent to standard RC₁, yielding syntactic proofs of known results on conservativity and computational complexity, whilst also establishing new findings on uniform interpolation. We sketch a generalisation to RCΛ, which proves sound but incomplete.
Eliminating cuts from non-nested reflection calculi / Joosten Joost, J., Perini Brogi, C.. - (In corso di stampa). (Proof Society 2026 - 8th International School and Workshop on Proof Theory Aussois, France 7-11/09/2026).
Eliminating cuts from non-nested reflection calculi
Perini Brogi Cosimo
In corso di stampa
Abstract
This paper introduces three cut-free sequent calculi for RC₁, the strictly positive fragment of Gödel-Löb's provability logic. We establish cut admissibility for all three systems—G1RC1, G1K4⁺, and G1K4⁺—which differ in their treatment of modal rules for necessitation and diamond transitivity. The calculi operate on single formulas rather than multisets, answering an open question about non-nested proof systems for reflection calculi. We demonstrate that our systems are equivalent to standard RC₁, yielding syntactic proofs of known results on conservativity and computational complexity, whilst also establishing new findings on uniform interpolation. We sketch a generalisation to RCΛ, which proves sound but incomplete.| File | Dimensione | Formato | |
|---|---|---|---|
|
ps26-16.pdf
embargo fino al 07/09/2026
Descrizione: Eliminating cuts from non-nested reflection calculi
Tipologia:
Abstract
Licenza:
Creative commons
Dimensione
210.29 kB
Formato
Adobe PDF
|
210.29 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


