A Multi-Focused Proof System Isomorphic to Expansion Proofs

Kaustuv Chaudhuri 1 Stefan Hetzl 1 Dale Miller 1, 2
1 PARSIFAL - Proof search and reasoning with logic specifications
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : The sequent calculus is often criticized for requiring proofs to contain large amounts of low-level syntactic details that can obscure the essence of a given proof. Because each inference rule introduces only a single connective, sequent proofs can separate closely related steps---such as instantiating a block of quantifiers---by irrelevant noise. Moreover, the sequential nature of sequent proofs forces proof steps that are syntactically non-interfering and permutable to nevertheless be written in some arbitrary order. The sequent calculus thus lacks a notion of canonicity: proofs that should be considered essentially the same may not have a common syntactic form. To fix this problem, many researchers have proposed replacing the sequent calculus with proof structures that are more parallel or geometric. Proof-nets, matings, and atomic flows are examples of such revolutionary formalisms. We propose, instead, an evolutionary approach to recover canonicity within the sequent calculus, which we illustrate for classical first-order logic. The essential element of our approach is the use of a multi-focused sequent calculus as the means for abstracting away low-level details from classical cut-free sequent proofs. We show that, among the multi-focused proofs, the maximally multi-focused proofs that collect together all possible parallel foci are canonical. Moreover, if we start with a certain focused sequent proof system, such proofs are isomorphic to expansion proofs---a well known, minimalistic, and parallel generalization of Herbrand disjunctions---for classical first-order logic. This technique appears to be a systematic way to recover the "essence of proof" from within sequent calculus proofs.
Type de document :
Article dans une revue
Journal of Logic and Computation, Oxford University Press (OUP), 2014
Liste complète des métadonnées

Contributeur : Kaustuv Chaudhuri <>
Soumis le : lundi 27 janvier 2014 - 16:58:39
Dernière modification le : mercredi 14 novembre 2018 - 16:14:01
Document(s) archivé(s) le : dimanche 27 avril 2014 - 23:45:12


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00937056, version 1



Kaustuv Chaudhuri, Stefan Hetzl, Dale Miller. A Multi-Focused Proof System Isomorphic to Expansion Proofs. Journal of Logic and Computation, Oxford University Press (OUP), 2014. 〈hal-00937056〉



Consultations de la notice


Téléchargements de fichiers