**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Cut-elimination theorem

Summary

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.
The cut rule
A sequent is a logical expression relating multiple formulas, in the form "A_1, A_2, A_3, \ldots \vdash B_1, B_2, B_3, \ldots", which is to be read as "A_1, A_2, A_3, \ldots proves B_1, B_2, B_3, \ldots", and (as glossed by Gentzen) should be understood as equivalent to the truth-function "If (A_1

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

Related people

No results

No results

Related units

Related concepts

No results

No results

Related courses

Related lectures

No results

No results