Sequent calculus

One of the formulations of the predicate calculus. Due to the convenient representation of derivations, the sequent calculus has wide applications in proof theory, in the foundations of mathematics and in the automatic search for a deduction. The sequent calculus was introduced by G. Gentzen in 1934 (see [1]). One version of the classical calculus of predicates in the form of the sequent calculus is presented below.

A collection of formulas is a finite set $ \Gamma $ of formulas of a certain logico-mathematical language $ \Omega $, where in this set, repetitions of formulas are permitted. The order of the formulas in $ \Gamma $ is inessential, but for each formula, the number of copies of it that are in $ \Gamma $ is given. The collection of formulas can be empty. The set $ \phi \Gamma $ is obtained from $ \Gamma $ by adjoining a copy of the formula $ \phi $. For two collections of formulas $ \Gamma $ and $ \Delta $, a figure of the form $ \Gamma \rightarrow \Delta $ is called a sequent; $ \Gamma $ is called the antecedent and $ \Delta $ the successor of the sequent.

The axioms of the sequent calculus have the form $ \phi \Gamma \rightarrow \Delta \phi $, where $ \Gamma $ and $ \Delta $ are arbitrary collections of formulas and $ \phi $ is an arbitrary atomic (elementary) formula. The derivation rules of the calculus have a very symmetrical structure; logical connectives are introduced into the sequent calculus by the following schemata:

$$ ( \wedge \rightarrow) \ \frac{\phi \psi \Gamma \rightarrow \Delta }{( \phi \wedge \psi ) \Gamma \rightarrow \Delta } ; \ \ (\rightarrow \wedge ) \ \frac{\Gamma \rightarrow \Delta \phi ; \Gamma \rightarrow \Delta \psi }{\Gamma \rightarrow \Delta ( \phi \wedge \psi ) } ; $$

$$ ( \lor \rightarrow) \frac{\phi \Gamma \rightarrow \Delta ; \psi \Gamma \rightarrow \Delta }{( \phi \lor \psi ) \Gamma \rightarrow \Delta } ; \ (\rightarrow \lor ) \frac{\Gamma \rightarrow \Delta \phi \psi }{\Gamma \rightarrow \Delta ( \phi \lor \psi ) } ; $$

$$ ( \supseteq \rightarrow ) \frac{\Gamma \rightarrow \Delta \phi ; \psi \Gamma \rightarrow \Delta }{( \phi \supseteq \psi ) \Gamma \rightarrow \Delta } ; \ (\rightarrow \supseteq ) \frac{\phi \Gamma \rightarrow \Delta \psi }{\Gamma \rightarrow \Delta ( \phi \supseteq \psi ) } ; $$

$$ ( \neg \rightarrow) \frac{\Gamma \rightarrow \Delta \phi }{\neg \phi \Gamma \rightarrow \Delta } ; \ (\rightarrow \neg ) \frac{\phi \Gamma \rightarrow \Delta }{\Gamma \rightarrow \Delta \neg \phi } ; $$

$$ ( \forall \rightarrow) \frac{\forall x \phi \phi ( x \mid t) \Gamma \rightarrow \Delta }{\forall x \phi \Gamma \rightarrow \Delta } ; \ (\rightarrow \forall ) \frac{\Gamma \rightarrow \Delta \phi }{\Gamma \rightarrow \Delta \forall x \phi ( y\mid x) } ; $$

$$ ( \exists \rightarrow) \frac{\phi \Gamma \rightarrow \Delta }{\exists x \phi ( y \mid x) \Gamma \rightarrow \Delta } ; \ (\rightarrow \exists ) \ \frac{\Gamma \rightarrow \Delta \phi ( x \mid t) \exists x \phi }{\Gamma \rightarrow \Delta \exists x \phi } . $$

In the rules $ (\rightarrow \forall ) $ and $ ( \exists \rightarrow) $ it is assumed that the variable $ y $ is not free in $ \Gamma $ or $ \Delta $, and that $ x $ is not free in $ \phi $.

The sequent calculus is equivalent to the usual form of predicate calculus, in the sense that a formula $ \phi $ is deducible in the predicate calculus if and only if the sequent $ \rightarrow \phi $ is deducible in the sequent calculus. The fundamental theorem of Gentzen (or the normalization theorem) is essential for the proof of this assertion; this theorem can be stated as follows: If the sequents $ \Gamma \rightarrow \Delta \phi $ and $ \phi \Gamma \rightarrow \Delta $ are deducible in the sequent calculus, then so is $ \Gamma \rightarrow \Delta $. The derivation rule

$$ \frac{\Gamma \rightarrow \Delta \phi ; \phi \Gamma \rightarrow \Delta }{\Gamma \rightarrow \Delta } $$

is called the cut rule, and the normalization theorem asserts that the cut rule is admissible in the sequent calculus, or that the addition of the cut rule does not change the collection of deducible sequents. In view of this, Gentzen's theorem is also called the cut-elimination theorem.

The symmetric structure of the sequent calculus greatly facilitates the study of its properties. Therefore, an important place in proof theory is occupied by the search for sequent variants of applied calculi: arithmetic, analysis, type theory, and also the proof for such calculi of the cut-elimination theorem in one form or another (see [2], [3]). Sequent variants can also be found for many calculi based on non-classical logics: intuitionistic, modal, relevance logics, and others (see [3], [4]).

References[edit]

Comments[edit]

Intuitively, the sequent $ \Gamma \rightarrow \Delta $ expresses that if all the formulas in $ \Gamma $ hold, then at least one of those in $ \Delta $ must also hold.

References[edit]