Cut-elimination theorem

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 his landmark 1934 paper "Investigations in Logical Deduction" for the systems LJ and LK formalising intuitionistic and classical logic respectively. The cut-elimination theorem states that any judgement 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.[1][2]

  1. ^ Curry 1977, pp. 208–213, gives a 5-page proof of the elimination theorem. See also pages 188, 250.
  2. ^ Kleene 2009, pp. 453, gives a very brief proof of the cut-elimination theorem.