A Semantical Analysis of Focusing and Contraction in Intuitionistic Logic

Issue title: Special Issue on the Italian Conference on Computational Logic: CILC 2013

Article type: Research Article

Authors: Avellone, Alessandro^{a; *} | Fiorentini, Camillo^b | Momigliano, Alberto^b

Affiliations: [a] Dipartimenti di Statistica e Metodi Quantitativi, Università degli Studi di Milano-Bicocca, Italy. alessandro.avellone@unimib.it | [b] Dipartimento di Informatica, Università degli Studi di Milano, Italy. fiorentini@di.unimi.it; momigliano@di.unimi.it

Correspondence: [*] Address for correspondence: Dipartimenti di Statistica e Metodi Quantitativi, Università degli Studi di Milano-Bicocca, Italy

Abstract: Focusing is a proof-theoretic device to structure proof search in the sequent calculus: it provides a normal form to cut-free proofs in which the application of invertible and non-invertible inference rules is structured in two separate and disjoint phases. Although stemming from proof-search considerations, focusing has not been thoroughly investigated in actual theorem proving, in particular w.r.t. termination. We present a contraction-free (and hence terminating) focused multi-succedent sequent calculus for propositional intuitionistic logic, which refines the G4ip calculus in the tradition of Vorob’ev, Hudelmeier and Dyckhoff. We prove completeness of the calculus semantically and argue that this offers a viable alternative to other more syntactical means.

DOI: 10.3233/FI-2015-1253

Journal: Fundamenta Informaticae, vol. 140, no. 3-4, pp. 247-262, 2015