The cut-elimination theorem
Authors:
- Paolo MancosuPMPaolo Mancosu
- Sergio GalvanSGSergio Galvan
- Richard ZachRZRichard Zach
- 17 August 2021
- book chapter
- Published by Oxford University Press (OUP)
- p. 202-268
Abstract
All the rules of the sequent calculus have the property that all the formulas that are present in the premises also occur in the conclusion. There is only one exception, the cut rule. In this chapter, it is shown using double induction that every theorem provable in Gentzen’s sequent calculi using the cut rule can also be proved without. One first proves that the mix rule is equivalent in proof-theoretic strength to the cut rule. Then one proves by induction on two complexity measures, the degree and the rank of a mix, that every application of mix can be eliminated. Several results follow from the cut-elimination theorem, including the so-called “mid-sequent” theorem and Herbrand’s theorem. In addition, one can prove the consistency of minimal, intuitionistic, and classical logic.Keywords
This publication has 40 references indexed in Scilit:
- Church–Rosser property of a simple reduction for full first-order classical natural deductionAnnals of Pure and Applied Logic, 2003
- Accessible Independence Results for Peano ArithmeticBulletin of the London Mathematical Society, 1982
- Über das Verhältnis zwischen intuitionistischer und klassischer ArithmetikArchive for Mathematical Logic, 1974
- Der erste Widerspruchsfreiheitsbeweis für die klassische ZahlentheorieArchive for Mathematical Logic, 1974
- Consistency Proofs of Subsystems of Classical AnalysisAnnals of Mathematics, 1967
- Systems of predicative analysisThe Journal of Symbolic Logic, 1964
- On the restricted ordinal theoremThe Journal of Symbolic Logic, 1944
- Untersuchungen ber das logische Schlie en. IIMathematische Zeitschrift, 1935
- Untersuchungen ber das logische Schlie en. IMathematische Zeitschrift, 1935
- Sur la non-contradiction de l'Arithmétique.Journal für die reine und angewandte Mathematik (Crelles Journal), 1932