A procedure in proof theory that transforms a sequent (or natural deduction) proof to remove cut inferences (applications of the 'cut' rule), producing a cut-free proof typically satisfying the subformula property.

Principle

Cuts act as lemmas that can be introduced and then used to shorten proofs; cut elimination systematically replaces cuts by expansions of their proofs so that every formula in the transformed proof is a subformula of the end sequent, often achieved by reducing a measure of cut complexity until no cuts remain.

Demonstration

Gentzen's Hauptsatz: in sequent calculi LK (classical) and LJ (intuitionistic), there is a procedure that eliminates cuts. For example, a proof that uses a cut on A can be transformed by composing the derivations of A's premise and conclusion and then permuting and simplifying inference steps until the cut disappears, at the cost of possibly increasing proof length.

Misapplication

Assuming cut elimination always yields a smaller or computationally simpler proof is incorrect — the elimination procedure can cause an exponential or non-elementary blow-up in proof size. Using cut elimination naively in systems with induction or certain fixed-point principles may fail or require additional meta-arguments.

Consequence

When applicable, cut elimination yields consistency proofs, the subformula property that supports decidability or complexity bounds for fragments, and a constructive interpretation of proofs as normalized computations; it also underpins interpolation and conservativity results in proof theory.

Reversal

Introducing cuts (lemmas) into a cut-free proof is the reversal: cuts can compress proofs and make them more modular. The tension between cut-free analyticity and cut-based proof economy reveals complementary roles of normalization and proof engineering.

Boundary

The standard cut-elimination theorems apply to well-specified sequent calculi or natural deduction systems without certain strong axioms; extensions to systems with induction, certain modal or fixed-point operators, or non-classical structural rules may be partial, require stratified approaches, or fail altogether.

Semantic Tension

Competes with the pragmatic use of cuts as proof abbreviations: theoretic purity (cut-free, analytic proofs) versus practical succinctness (using cuts to keep proofs human- or machine-manageable). There is also tension between syntactic normalization and semantic models where cuts correspond to computational effects.

Synthesis

Cut elimination is a syntactic normalization method that removes non-analytic inferences by expanding and permuting proof structure to achieve the subformula property; it is foundational for meta-theoretical results (consistency, interpolation) but may trade off proof size and practical efficiency.