cut-elimination theorem
E846922
The cut-elimination theorem is a fundamental result in proof theory showing that any proof using the cut rule can be transformed into a cut-free proof, thereby clarifying the constructive content and consistency of formal systems.
All labels observed (1)
| Label | Occurrences |
|---|---|
| cut-elimination theorem canonical | 1 |
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf | theorem in proof theory ⓘ |
| alsoKnownAs |
Gentzen’s Hauptsatz
NERFINISHED
ⓘ
Hauptsatz NERFINISHED ⓘ |
| appliesTo |
Gentzen-style proof systems
ⓘ
classical logic sequent calculi ⓘ intuitionistic logic sequent calculi ⓘ many substructural logics ⓘ sequent calculus ⓘ |
| clarifies | constructive content of proofs ⓘ |
| concernsConcept | cut-free proof ⓘ |
| concernsRule | cut rule ⓘ |
| field |
mathematical logic
ⓘ
proof theory ⓘ |
| formalizedIn |
Gentzen’s sequent calculus LJ
NERFINISHED
ⓘ
Gentzen’s sequent calculus LK NERFINISHED ⓘ |
| generalizedBy |
cut-elimination for higher-order logics
ⓘ
cut-elimination for infinitary calculi ⓘ |
| hasConsequence |
canonicity of proof structure
ⓘ
elimination of detours in proofs ⓘ |
| hasKeyIdea | eliminate intermediate lemmas represented by cuts ⓘ |
| hasVariant |
partial cut-elimination
ⓘ
semantic cut-elimination ⓘ syntactic cut-elimination ⓘ |
| implies |
consistency of certain formal systems
ⓘ
subformula property for cut-free proofs ⓘ |
| influencedField |
automated theorem proving
ⓘ
proof mining ⓘ structural proof theory NERFINISHED ⓘ type theory ⓘ |
| introducedBy | Gerhard Gentzen NERFINISHED ⓘ |
| involves |
reduction of cut rank
ⓘ
reduction of proof height ⓘ |
| motivated | Gentzen’s consistency proof for arithmetic NERFINISHED ⓘ |
| relatedTo |
Herbrand’s theorem
NERFINISHED
ⓘ
normalization theorem for natural deduction ⓘ ordinal analysis ⓘ |
| requires | well-founded measure on proofs for reduction ⓘ |
| shows | cuts are inessential for derivability in suitable systems ⓘ |
| statesThat | every proof using the cut rule can be transformed into a cut-free proof ⓘ |
| supports | constructivist interpretations of proofs ⓘ |
| usedFor |
analysis of proof complexity
ⓘ
consistency proofs ⓘ program extraction from proofs ⓘ proof normalization ⓘ subformula property results ⓘ |
| yearProved | 1934 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.