Sequent calculus — Safekipedia Adventurer

In mathematical logic, sequent calculus is a way to write out logical arguments step-by-step. Each step is a special kind of statement, called a sequent, created by Gerhard Gentzen. These steps connect to each other using clear rules, which helps show how mathematicians reason.

Sequent calculus is one way to show logical arguments. It is different from David Hilbert's older style of formal logic. In Hilbert's style, every step must always be true. In sequent calculus, each step can depend on earlier steps. This is more like how real mathematicians work.

There are different styles for these step-by-step proofs. In natural deduction, each step shows one result. In sequent calculus, each step can show many results together. Both of these styles, called Gentzen-style systems, have fewer basic rules. They use the steps more than many starting ideas.

Gentzen-style systems, like sequent calculus, are very useful. They help with statements that have quantifiers, such as "for all" or "there exists." They do this by temporarily removing these words, using simpler rules, and then adding them back. This is similar to how mathematicians write proofs and often makes arguments shorter and easier to follow. While natural deduction is good for solving problems, sequent calculus is helpful for studying the logic of arguments in theory.

Overview

In proof theory and mathematical logic, sequent calculus is a way to build logical arguments. It was first created in 1934/1935 by Gerhard Gentzen. He made two main systems, LK for classical logic and LJ for intuitionistic logic.

The main idea of sequent calculus is that each step in a proof shows a link between groups of statements, called a "sequent." This helps us see how ideas connect better than older methods. Gentzen’s work showed that sequent calculus could prove important facts about some mathematical systems.

Hilbert-style deduction systems

Main article: Hilbert system

One way to build logical proofs is called Hilbert-style. In this method, each step is a single statement that comes from earlier ones. But these proofs can become very long and hard to follow. To make them simpler, mathematicians created 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 one statement on the right. This copies how people usually think, which makes 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 builds on this idea. Instead of one statement on the right, it allows many statements. This makes the logic more balanced and easier to study. For example, if all statements on the left are true, then at least one on the right must also be true. This balance helps us find hidden patterns in logical thinking.

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.

For example, to prove a formula like (((p \rightarrow r) \lor (q \rightarrow r)) \rightarrow ((p \land q) \rightarrow r)), we start by assuming one part and then try to prove another part. We keep breaking down the formula until we reach simple facts that are true or false. This process can be shown as a tree.

This method helps mathematicians check if a formula is true.

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 changing what can be proven. For example, sequents can be seen 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