##  [Cut Elimination](/cut-elimination-1) 

 Definition

The proof transformation that removes cut inferences (applications of the cut rule) from a sequent-calculus style proof to produce a cut-free derivation of the same end-sequent, preserving provability while often changing proof structure and size.

 

 

 

 

 

 





## Principle

Principle

Permute and simplify inferences so that every application of the cut rule is successively eliminated by replacing it with derivations that only use subformulas of the goal; this preserves provability and yields analytic proofs typically enjoying the subformula property.

 

 

 

 

 





## Demonstration

Demonstration

In Gentzen's sequent calculus, a proof that uses a cut on formula A can be transformed by replacing the cut with derivations of A's subformulas from the premises and composing them, resulting in a proof of the same sequent without the cut; repeated application removes all cuts.

 

 

 

 

## Misapplication

Misapplication

Assuming cut elimination preserves proof length, complexity class, or algorithmic feasibility in general; using it to claim decidability where the system still has undecidable fragments, or ignoring that elimination may exponentially blow up proof size or introduce non-constructive steps in some settings.

 

 

 

 

 





## Consequence

Consequence

Cut elimination yields cut-free proofs with the subformula property, enabling consistency proofs, interpolation results, and finer proof analysis; it implies that lemmas introduced by cuts are admissible rather than essential for provability in the system at hand.

 

 

 

 

## Reversal

Reversal

In contrast, allowing cuts is the practice of lemma introduction: adding cut can drastically shorten proofs and provide modularity and reuse, so the reversal emphasizes proof compactness and human-oriented structure rather than analytic form.

 

 

 

 

 





## Boundary

Boundary

Cut elimination holds in many structural proof systems like Gentzen's LK and LJ under standard logical rules, but may fail or require modification in systems with certain non-standard rules, fixed points, or inductive definitions; complexity and termination must be considered separately.

 

 

 

 

 





## Semantic Tension

Semantic Tension

There is tension between eliminating cuts to obtain analytic proofs and retaining cuts to preserve brevity and structure; analyticity trades off compactness for subformula-based reasoning, and practical theorem proving often reintroduces lemmas (cuts) for efficiency.

 

 

 

 

 





## Synthesis

Synthesis

Cut elimination is the systematic removal of non-analytic inferences from sequent-calculus proofs: by transforming and permuting rules to eliminate cuts, it produces analytically structured proofs that expose subformula dependencies at the cost, sometimes, of increased size or altered constructive content.