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.
In corso di stampa
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11771/43739
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • OpenAlex ND
social impact