A formalization of Sambins's normalization for GL

✍ Scribed by Edward Hermann Haeusler; Luiz Carlos Pereira

• Book ID: 102940861
• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 529 KB
• Volume: 39
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19930390116

✦ Synopsis

Abstract

Sambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut‐free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B45.