Concept

Cut-elimination theorem

Overview

The cut-elimination theorem (or Gentzen's Hauptsatz) is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in part I of his landmark 1935 paper "Investigations in Logical Deduction" for the systems LJ and LK formalising intuitionistic and classical logic respectively. The cut-elimination theorem states that any sequent that possesses a proof in the sequent calculus making use of the cut rule also possesses a cut-free proof, that is, a proof that does not make use of the cut rule. The natural deduction version of cut-elimination, known as the normalization theorem, was first proved for a variety of logics by Dag Prawitz in 1965 (a similar but less general proof was given the same year by Andrès Raggio).

There are many different possible sequent calculuses for many logics, and consequently there are many different cut-elimination theorems. Indeed, cut-elimination is such an important genre of theorems in logic, that logicians speak of "this logic has cut-elimination" as a way to say that this logic has a desirable property. Conversely, if a formalism or a logic does not have cut-elimination, that is usually considered a point against it, and would motivate research into finding a new formalism, or a modification of the logic, such that cut-elimination is true, or an analog of cut-elimination is true.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

1. Yet they are full of unexamined assumptions; they commit us to all sorts of logically predetermined conclusions. In one sense our study of the new subject-matter, let us say logical theory, is in truth only a review, a retesting and criticizing of the intellectual standpoints and methods which we bring with us to the study.

   John Dewey, Essays in Experimental Logic

   Close in meaning to Cut-elimination theorem; the term itself is not named.

   Read the chapter · Open in the reader

2. Sec. 4. THE PLACE OF GENERAL RULES Between such a highly generalized and formal principle as that of Kant, and the judgment of particular cases, we have intermediate generalizations; rules which are broad as compared with individual deeds, but narrow as compared with some one final principle. What are their rational origin, place, and function?

   John Dewey, Ethics

   Close in meaning to Cut-elimination theorem; the term itself is not named.

   Read the chapter · Open in the reader

3. The transcendental conception of reason is therefore nothing else than the conception of the totality of the conditions of a given conditioned. Now as the unconditioned alone renders possible totality of conditions, and, conversely, the totality of conditions is itself always unconditioned; a pure rational conception in general can be defined and explained by means of the conception of the unconditioned, in so far…

   Immanuel Kant, The Critique of Pure Reason

   States what Cut-elimination theorem is.

   Read the chapter · Open in the reader

Philosophers who discussed Cut-elimination theorem

• Stanisław Jaśkowski

Related ideas

• First-order logic
• Intuitionistic logic
• Law of excluded middle
• Proof theory
• Mathematical object
• Prolog
• Peano axioms
• Rule of inference
• Sequent calculus
• Curry–Howard correspondence
• George Boolos
• Tautology (logic)
• Natural deduction
• Classical logic
• Consistency
• Contradiction
• Jean-Yves Girard
• Structural rule
• Dag Prawitz
• Multiset

Place in the tradition

Part of Linear logic.

Explore Cut-elimination theorem in the interactive graph →