What is a cut in a proof?

The cut rule allows one to prove a lemma and then use it: from a derivation establishing a formula and another using that formula as a premise, it concludes the combined result. Cut-elimination shows such intermediate lemmas can always be removed in principle.

Why can eliminating cuts make proofs much longer?

Removing a cut may require duplicating large parts of a derivation, and iterating this can blow up the proof size by a tower of exponentials. So cut-free proofs are conceptually simpler but can be vastly larger than the original proofs with cuts.

Cut-Elimination

Cut-elimination is Gentzen's theorem that the cut rule, which formalizes the use of lemmas, can be removed from any sequent calculus proof, leaving a proof built only from the formulas it concerns.

Definition

Cut-elimination is the theorem and the constructive procedure showing that any sequent calculus derivation using the cut rule can be transformed into one that does not, so that every provable sequent has a proof in which only subformulas of the end sequent appear.

Scope

This topic covers the cut rule and its role in the sequent calculus, the cut-elimination procedure and its termination, the subformula property of cut-free proofs, the resulting consistency and decidability consequences, and the bounds on proof size that elimination can incur.

Core questions

What does the cut rule express and why is its removal significant?
How does the cut-elimination procedure terminate?
What is the subformula property and what does it imply for proof search?
What is the computational cost of eliminating cuts?

Key theories

Gentzen Hauptsatz: Gentzen's principal theorem states that the cut rule is admissible in the sequent calculus, so any proof using cuts can be converted to a cut-free proof of the same end sequent.
Subformula property: Every formula occurring in a cut-free proof is a subformula of the end sequent, which constrains proof shape and underlies decision procedures and consistency arguments.
Consistency via cut-elimination: Because a cut-free proof of the empty sequent is impossible, cut-elimination yields a direct proof that the calculus, and hence the theory it formalizes, is consistent.

Clinical relevance

Cut-elimination is a foundational result with broad consequences: it yields consistency proofs, the subformula property essential to automated theorem proving and tableau methods, interpolation theorems, and, through the proofs-as-programs correspondence, the normalization of typed programs.

History

Gentzen proved cut-elimination, his Hauptsatz, in 1934 for first-order logic, and the method became the cornerstone of structural proof theory. Tait and Girard extended the technique to stronger systems and higher-order logic, and the bounds on the growth of proof size under cut-elimination became a subject of study in their own right.

Key figures

Gerhard Gentzen
William Tait
Jean-Yves Girard
Gaisi Takeuti

Seminal works

takeuti1987
troelstra2000
negri2001

Frequently asked questions

What is a cut in a proof?: The cut rule allows one to prove a lemma and then use it: from a derivation establishing a formula and another using that formula as a premise, it concludes the combined result. Cut-elimination shows such intermediate lemmas can always be removed in principle.
Why can eliminating cuts make proofs much longer?: Removing a cut may require duplicating large parts of a derivation, and iterating this can blow up the proof size by a tower of exponentials. So cut-free proofs are conceptually simpler but can be vastly larger than the original proofs with cuts.