[Back]

K. Chaudhuri, S. Hetzl, D. Miller:
"A multi-focused proof system isomorphic to expansion proof";
Journal of Logic and Computation, 26 (2016), 2; 577 - 603.

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 formalizms. 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.

multi-focusing, expansion trees, canonicity

http://dx.doi.org/10.1093/logcom/exu030