A cut-free sequent system for Grzegorczyk logic, with an application to the Godel-McKinsey-Tarski embedding

摘要

It is well-known that intuitionistic propositional logic Int may be faithfully embedded not just into the modal logic S4 but also into the provability logics GL and Grz of Godel-Lob and Grzegorczyk, and also that there is a similar embedding of Grz into GL. Known proofs of these faithfulness results are short but model-theoretic and thus non-constructive. Here a labelled sequent system Grz for Grzegorczyk logic is presented and shown to be complete and therefore closed with respect to Cut. The completeness proof, being constructive, yields a constructive decision procedure, i.e. both a proof procedure for derivable sequents and a countermodel construction for underivable sequents. As an application, a constructive proof of the faithfulness of the embedding of Int into Grz and hence a constructive decision procedure for Int are obtained.