Sequent calculus — Safekipedia Discoverer

In mathematical logic, sequent calculus is a special way of writing out logical arguments. Instead of each step in a proof being a statement that is always true, each step is a conditional statement, called a sequent, introduced by Gerhard Gentzen. These steps build on each other using specific rules, making it easier to follow the kind of reasoning mathematicians use.

Sequent calculus is one of several methods for showing logical arguments step-by-step. Unlike David Hilbert's earlier style of formal logic, where every step must be always true, sequent calculus lets each step depend on earlier steps. This makes it closer to how real mathematicians work.

There are different styles of these step-by-step proofs. In natural deduction, each step shows one result. In sequent calculus, each step can show many results at once. Both of these styles, called Gentzen-style systems, have fewer basic rules and rely more on these steps rather than on many starting assumptions.

Gentzen-style systems, like sequent calculus, are very useful. They make it easier to handle statements with quantifiers, such as "for all" or "there exists," by temporarily removing them, applying simpler rules, and then adding them back. This mirrors how mathematicians actually write proofs and often leads to shorter, easier-to-follow arguments. While natural deduction is better for practical problem-solving, sequent calculus is especially helpful for studying the logic behind these arguments in theory.

Overview

In proof theory and mathematical logic, sequent calculus is a family of formal systems that use a special way of building logical arguments. It was first introduced in 1934/1935 by Gerhard Gentzen as a tool for studying natural deduction in first-order logic. Gentzen created two main systems, LK for classical logic and LJ for intuitionistic logic.

The big idea behind sequent calculus is that each step in a proof shows a relationship between groups of statements, called a "sequent." This makes it easier to see how ideas connect compared to older methods. Gentzen’s work showed that sequent calculus could prove important results, like the consistency of certain mathematical systems, which was surprising at the time.

Hilbert-style deduction systems

Main article: Hilbert system

One simple way to build logical proofs is called Hilbert-style. In this method, each step is a single statement that follows from earlier ones. But these proofs can get very long and hard to follow. To make them easier, mathematicians developed other methods like natural deduction.

Natural deduction systems

Main article: Natural deduction

Natural deduction uses a list of statements on the left side of a symbol (⊢) and a single statement on the right. This mimics how people naturally reason, making proofs easier to understand. For example, if you know several facts are true, you can use them to prove a new fact.

Sequent calculus systems

Finally, sequent calculus takes this idea further. Instead of one statement on the right, it allows many statements. This creates a balance between the two sides, making the logic more symmetric and easier to study. For instance, if all statements on the left are true, then at least one on the right must also be true. This symmetry helps reveal deeper patterns in logical reasoning.

Proving logical formulas

Sequent calculus is a way to prove logical formulas in propositional logic. It breaks down complex formulas into simpler parts step by step until they become very basic and easy to understand.

A rooted tree describing a proof finding procedure by sequent calculus

For example, to prove a formula like (((p \rightarrow r) \lor (q \rightarrow r)) \rightarrow ((p \land q) \rightarrow r)), we start by assuming the part before the arrow (((p \rightarrow r) \lor (q \rightarrow r))) and then try to prove the part after the arrow (((p \land q) \rightarrow r)). We keep breaking down the formula into smaller pieces until we reach simple, basic facts that are obviously true or false. This process can be shown as a tree, where the starting formula is at the top, and the simple facts are at the bottom.

This method helps mathematicians and logicians check if a formula is true by seeing if it can be broken down into pieces that match up perfectly.

Left	Right
L ∧ rule: Γ , A ∧ B ⊢ Δ Γ , A , B ⊢ Δ {\displaystyle L\land {\text{rule: }}\quad {\cfrac {\Gamma ,A\land B\vdash \Delta }{\Gamma ,A,B\vdash \Delta }}}	R ∧ rule: Γ ⊢ Δ , A ∧ B Γ ⊢ Δ , A Γ ⊢ Δ , B {\displaystyle R\land {\text{rule: }}{\cfrac {\Gamma \vdash \Delta ,A\land B}{\Gamma \vdash \Delta ,A\qquad \Gamma \vdash \Delta ,B}}}
L ∨ rule: Γ , A ∨ B ⊢ Δ Γ , A ⊢ Δ Γ , B ⊢ Δ {\displaystyle L\lor {\text{rule: }}{\cfrac {\Gamma ,A\lor B\vdash \Delta }{\Gamma ,A\vdash \Delta \qquad \Gamma ,B\vdash \Delta }}}	R ∨ rule: Γ ⊢ Δ , A ∨ B Γ ⊢ Δ , A , B {\displaystyle R\lor {\text{rule: }}\quad {\cfrac {\Gamma \vdash \Delta ,A\lor B}{\Gamma \vdash \Delta ,A,B}}}
L → rule: Γ , A → B ⊢ Δ Γ ⊢ A Γ , B ⊢ Δ {\displaystyle L\rightarrow {\text{rule: }}{\cfrac {\Gamma ,A\rightarrow B\vdash \Delta }{\Gamma \vdash A\qquad \Gamma ,B\vdash \Delta }}}	R → rule: Γ ⊢ Δ , A → B Γ , A ⊢ Δ , B {\displaystyle R\rightarrow {\text{rule: }}\quad {\cfrac {\Gamma \vdash \Delta ,A\rightarrow B}{\Gamma ,A\vdash \Delta ,B}}}
L ¬ rule: Γ , ¬ A ⊢ Δ Γ ⊢ Δ , A {\displaystyle L\lnot {\text{rule: }}\quad {\cfrac {\Gamma ,\lnot A\vdash \Delta }{\Gamma \vdash \Delta ,A}}}	R ¬ rule: Γ ⊢ Δ , ¬ A Γ , A ⊢ Δ {\displaystyle R\lnot {\text{rule: }}\quad {\cfrac {\Gamma \vdash \Delta ,\lnot A}{\Gamma ,A\vdash \Delta }}}
Axiom: Γ , A ⊢ Δ , A {\displaystyle \Gamma ,A\vdash \Delta ,A}

The system LK

The system LK, introduced by Gentzen in 1934, is a way to build logical proofs step by step. Each step, called a sequent, builds on earlier steps using specific rules. This method closely matches how mathematicians naturally reason.

The rules in LK are divided into two groups: logical rules and structural rules. Logical rules introduce new statements on either side of the turnstile (⊢), which separates assumptions from conclusions. Structural rules manage the order and grouping of these statements. For example, the rule (∧ L) shows that if you can prove something using assumption A, you can also prove it using the stronger assumption A ∧ B. Similarly, the rule (¬ R) helps prove that if assuming A leads to a conclusion, then not A might also be true. These rules provide clear, step-by-step ways to build logical arguments.

Axiom	Cut
A ⊢ A ( I ) {\displaystyle {\cfrac {\qquad }{A\vdash A}}\quad (I)}	Γ ⊢ Δ , A A , Σ ⊢ Π Γ , Σ ⊢ Δ , Π ( C u t ) {\displaystyle {\cfrac {\Gamma \vdash \Delta ,A\qquad A,\Sigma \vdash \Pi }{\Gamma ,\Sigma \vdash \Delta ,\Pi }}\quad ({\mathit {Cut}})}

Left logical rules	Right logical rules
Γ , A ⊢ Δ Γ , A ∧ B ⊢ Δ ( ∧ L 1 ) {\displaystyle {\cfrac {\Gamma ,A\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }}\quad ({\land }L_{1})}	Γ ⊢ A , Δ Γ ⊢ A ∨ B , Δ ( ∨ R 1 ) {\displaystyle {\cfrac {\Gamma \vdash A,\Delta }{\Gamma \vdash A\lor B,\Delta }}\quad ({\lor }R_{1})}
Γ , B ⊢ Δ Γ , A ∧ B ⊢ Δ ( ∧ L 2 ) {\displaystyle {\cfrac {\Gamma ,B\vdash \Delta }{\Gamma ,A\land B\vdash \Delta }}\quad ({\land }L_{2})}	Γ ⊢ B , Δ Γ ⊢ A ∨ B , Δ ( ∨ R 2 ) {\displaystyle {\cfrac {\Gamma \vdash B,\Delta }{\Gamma \vdash A\lor B,\Delta }}\quad ({\lor }R_{2})}
Γ , A ⊢ Δ Γ , B ⊢ Δ Γ , A ∨ B ⊢ Δ ( ∨ L ) {\displaystyle {\cfrac {\Gamma ,A\vdash \Delta \qquad \Gamma ,B\vdash \Delta }{\Gamma ,A\lor B\vdash \Delta }}\quad ({\lor }L)}	Γ ⊢ A , Δ Γ ⊢ B , Δ Γ ⊢ A ∧ B , Δ ( ∧ R ) {\displaystyle {\cfrac {\Gamma \vdash A,\Delta \qquad \Gamma \vdash B,\Delta }{\Gamma \vdash A\land B,\Delta }}\quad ({\land }R)}
Γ ⊢ A , Δ Σ , B ⊢ Π Γ , Σ , A → B ⊢ Δ , Π ( → L ) {\displaystyle {\cfrac {\Gamma \vdash A,\Delta \qquad \Sigma ,B\vdash \Pi }{\Gamma ,\Sigma ,A\rightarrow B\vdash \Delta ,\Pi }}\quad ({\rightarrow }L)}	Γ , A ⊢ B , Δ Γ ⊢ A → B , Δ ( → R ) {\displaystyle {\cfrac {\Gamma ,A\vdash B,\Delta }{\Gamma \vdash A\rightarrow B,\Delta }}\quad ({\rightarrow }R)}
Γ , A ⊢ B , Δ Γ , A ∖ B ⊢ Δ ( ∖ L ) {\displaystyle {\cfrac {\Gamma ,A\vdash B,\Delta }{\Gamma ,A\setminus B\vdash \Delta }}\quad ({\setminus }L)}	Γ ⊢ A , Δ Σ , B ⊢ Π Γ , Σ ⊢ A ∖ B , Δ , Π ( ∖ R ) {\displaystyle {\cfrac {\Gamma \vdash A,\Delta \qquad \Sigma ,B\vdash \Pi }{\Gamma ,\Sigma \vdash A\setminus B,\Delta ,\Pi }}\quad ({\setminus }R)}
Γ ⊢ A , Δ Γ , ¬ A ⊢ Δ ( ¬ L ) {\displaystyle {\cfrac {\Gamma \vdash A,\Delta }{\Gamma ,\lnot A\vdash \Delta }}\quad ({\lnot }L)}	Γ , A ⊢ Δ Γ ⊢ ¬ A , Δ ( ¬ R ) {\displaystyle {\cfrac {\Gamma ,A\vdash \Delta }{\Gamma \vdash \lnot A,\Delta }}\quad ({\lnot }R)}
Γ , A [ t / x ] ⊢ Δ Γ , ∀ x A ⊢ Δ ( ∀ L ) {\displaystyle {\cfrac {\Gamma ,A[t/x]\vdash \Delta }{\Gamma ,\forall xA\vdash \Delta }}\quad ({\forall }L)}	Γ ⊢ A [ y / x ] , Δ Γ ⊢ ∀ x A , Δ ( ∀ R ) {\displaystyle {\cfrac {\Gamma \vdash A[y/x],\Delta }{\Gamma \vdash \forall xA,\Delta }}\quad ({\forall }R)} (†)
Γ , A [ y / x ] ⊢ Δ Γ , ∃ x A ⊢ Δ ( ∃ L ) {\displaystyle {\cfrac {\Gamma ,A[y/x]\vdash \Delta }{\Gamma ,\exists xA\vdash \Delta }}\quad ({\exists }L)} (†)	Γ ⊢ A [ t / x ] , Δ Γ ⊢ ∃ x A , Δ ( ∃ R ) {\displaystyle {\cfrac {\Gamma \vdash A[t/x],\Delta }{\Gamma \vdash \exists xA,\Delta }}\quad ({\exists }R)}

Left structural rules	Right structural rules
Γ ⊢ Δ Γ , A ⊢ Δ ( W L ) {\displaystyle {\cfrac {\Gamma \vdash \Delta }{\Gamma ,A\vdash \Delta }}\quad ({\mathit {WL}})}	Γ ⊢ Δ Γ ⊢ A , Δ ( W R ) {\displaystyle {\cfrac {\Gamma \vdash \Delta }{\Gamma \vdash A,\Delta }}\quad ({\mathit {WR}})}
Γ , A , A ⊢ Δ Γ , A ⊢ Δ ( C L ) {\displaystyle {\cfrac {\Gamma ,A,A\vdash \Delta }{\Gamma ,A\vdash \Delta }}\quad ({\mathit {CL}})}	Γ ⊢ A , A , Δ Γ ⊢ A , Δ ( C R ) {\displaystyle {\cfrac {\Gamma \vdash A,A,\Delta }{\Gamma \vdash A,\Delta }}\quad ({\mathit {CR}})}
Γ 1 , A , B , Γ 2 ⊢ Δ Γ 1 , B , A , Γ 2 ⊢ Δ ( P L ) {\displaystyle {\cfrac {\Gamma _{1},A,B,\Gamma _{2}\vdash \Delta }{\Gamma _{1},B,A,\Gamma _{2}\vdash \Delta }}\quad ({\mathit {PL}})}	Γ ⊢ Δ 1 , A , B , Δ 2 Γ ⊢ Δ 1 , B , A , Δ 2 ( P R ) {\displaystyle {\cfrac {\Gamma \vdash \Delta _{1},A,B,\Delta _{2}}{\Gamma \vdash \Delta _{1},B,A,\Delta _{2}}}\quad ({\mathit {PR}})}

		( I ) {\displaystyle (I)}
A ⊢ A {\displaystyle A\vdash A}
		( ¬ R ) {\displaystyle (\lnot R)}
⊢ ¬ A , A {\displaystyle \vdash \lnot A,A}
		( ∨ R 2 ) {\displaystyle (\lor R_{2})}
⊢ A ∨ ¬ A , A {\displaystyle \vdash A\lor \lnot A,A}
		( P R ) {\displaystyle (PR)}
⊢ A , A ∨ ¬ A {\displaystyle \vdash A,A\lor \lnot A}
		( ∨ R 1 ) {\displaystyle (\lor R_{1})}
⊢ A ∨ ¬ A , A ∨ ¬ A {\displaystyle \vdash A\lor \lnot A,A\lor \lnot A}
		( C R ) {\displaystyle (CR)}
⊢ A ∨ ¬ A {\displaystyle \vdash A\lor \lnot A}

		( I ) {\displaystyle (I)}
p ( x , y ) ⊢ p ( x , y ) {\displaystyle p(x,y)\vdash p(x,y)}
		( ∀ L ) {\displaystyle (\forall L)}
∀ x ( p ( x , y ) ) ⊢ p ( x , y ) {\displaystyle \forall x\left(p(x,y)\right)\vdash p(x,y)}
		( ∃ R ) {\displaystyle (\exists R)}
∀ x ( p ( x , y ) ) ⊢ ∃ y ( p ( x , y ) ) {\displaystyle \forall x\left(p(x,y)\right)\vdash \exists y\left(p(x,y)\right)}
		( ∃ L ) {\displaystyle (\exists L)}
∃ y ( ∀ x ( p ( x , y ) ) ) ⊢ ∃ y ( p ( x , y ) ) {\displaystyle \exists y\left(\forall x\left(p(x,y)\right)\right)\vdash \exists y\left(p(x,y)\right)}
		( ∀ R ) {\displaystyle (\forall R)}
∃ y ( ∀ x ( p ( x , y ) ) ) ⊢ ∀ x ( ∃ y ( p ( x , y ) ) ) {\displaystyle \exists y\left(\forall x\left(p(x,y)\right)\right)\vdash \forall x\left(\exists y\left(p(x,y)\right)\right)}

Variants

The rules of sequent calculus can be changed in different ways without affecting what can be proven. For example, sequents can be viewed as groups of statements, which makes some rules simpler.

One important variant is called intuitionistic sequent calculus, or System LJ. This system changes a few rules so that it only deals with statements that have one result on the right side. This makes it useful for studying certain types of logical statements and proving special properties, like disjunction and existence properties.

Main article: Substructural logic