Cut-Elimination Theorem

For a specified proof calculus, every derivation using an intermediate cut formula can be replaced by a cut-free derivation of the same end judgment, when the calculus satisfies the theorem's rule conditions.

Version

v1 · 2026-10-03 · History

Domain-specific #

13118

Aliases

Gentzens Hauptsatz

Core Idea

A cut-elimination theorem says that in a specified proof calculus, every derivation of an end sequent using the cut rule has a derivation of the same sequent without cut. Cut passes through an intermediate formula proved in one branch and used in another; the formula need not appear in the end judgment. Eliminability makes the rule admissible—it can organize a proof but adds no new derivable end sequents to that calculus.[^{ref-eaad21525167][}ref-deb03503ce80]

Scope of Application

Pfenning proves cut admissible in a displayed intuitionistic single-conclusion calculus by induction on both the cut formula and derivation structure. Moschovakis states a corresponding theorem for classical \(G\) and intuitionistic \(GI\), with first-order variable qualifications. Zach proves an extension for specifically constructed generalized connective calculi. None licenses an unconditional claim about every formal proof system.[^{ref-eaad21525167][}ref-deb03503ce80][^ref-1e42c5fe1080]

Clarity

The theorem is not the act of deleting a lemma line: a transformation must replace the inferential work and preserve the final judgment. Principal cuts can reduce to cuts on subformulas, while other cuts move across inference rules without immediately shrinking the formula. Familiar subformula and proof-search consequences require an analytic cut-free calculus; they are not automatic for arbitrary rules or extra axioms.[^{ref-eaad21525167][}ref-deb03503ce80]

Manages Complexity

Cut-free derivations expose how a goal follows through the remaining rules without guessing an arbitrary intermediate lemma. That can support structural analysis and proof search, but inlining lemma work can greatly enlarge a proof. Buss reports strong first-order lower bounds for cut-free proof size, so cut-free does not mean computationally cheaper.[^{ref-eaad21525167][}ref-eed7e1ace928]

Abstract Reasoning

In a schematic cut, one derivation proves \(A\) and another uses \(A\) to prove \(C\); the theorem constructs a proof of \(C\) without that intermediate rule. The induction must respect the exact logical and structural rules of the calculus. Natural-deduction normalization and typed-term evaluation have related proof-theoretic correspondences but are separate results with different objects and judgments.[^{ref-eaad21525167][}ref-1e42c5fe1080]

Knowledge Transfer

Classical, intuitionistic and some generalized sequent calculi can realize the same calculus/cut/transformation/cut-free-output pattern after separate proofs. Live Proof Calculus and prime Formal System are subjects of such a theorem, not theorem-level parents; live prime Cut concerns graph partitions. The workspace DAG proposal is therefore unparented pending a defensible genus. No canonical edge was changed.[^{ref-deb03503ce80][}ref-1e42c5fe1080]

[^ref-eaad21525167]: Frank Pfenning, Lecture Notes on Sequent Calculus, Carnegie Mellon University 15-816 Lecture 8 (9 February 2010), PDF pp. 8–10, §4 and Theorem 4. [^ref-deb03503ce80]: Yiannis N. Moschovakis, Lecture Notes in Logic, UCLA notes (29 March 2014), Chapter 3 §§3A–3C, especially PDF p. 116 Theorem 3C.1; notes self-label as informal, so the central result was cross-checked. [^ref-1e42c5fe1080]: Richard Zach, “Cut elimination and normalization for generalized single and multi-conclusion sequent and natural deduction calculi”, original research manuscript (2020), abstract and §§1, 6, 8. [^ref-eed7e1ace928]: Samuel R. Buss, “Sharpened Lower Bounds for Cut Elimination”, Journal of Symbolic Logic 77(2), 656–668 (2012), author publication-page abstract; direct full PDF was unavailable in this audit.

Neighborhood in Abstraction Space

Cut-Elimination Theorem sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Formal Models & Logical Foundations (33 abstractions)

Nearest neighbors

• Cut Rule — 0.89
• Proof calculus — 0.88
• Peirce's Law — 0.86
• Intuitionistic Type Theory — 0.86
• Formal Theory — 0.85

Computed from structural-signature embeddings · 2026-10-08