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 (2)
| Label | Occurrences |
|---|---|
| cut-elimination theorem canonical | 3 |
| cut elimination theorem | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T10197990 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: cut-elimination theorem Context triple: [Gerhard Gentzen, knownFor, cut-elimination theorem]
-
A.
Herbrand's theorem
Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.
-
B.
Curry–Howard correspondence
The Curry–Howard correspondence is a foundational principle in logic and computer science that establishes a deep analogy between proofs and programs, and between logical propositions and types in programming languages.
-
C.
Church–Rosser property
The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
-
D.
Löb's theorem
Löb's theorem is a fundamental result in mathematical logic that characterizes when a sufficiently strong formal system can prove statements about its own provability, closely refining the insights of Gödel’s incompleteness theorems.
-
E.
Gentzen’s consistency proof for arithmetic
Gentzen’s consistency proof for arithmetic is a landmark 1930s result in proof theory that established the consistency of Peano arithmetic using transfinite induction up to the ordinal ε₀.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: cut-elimination theorem Target entity description: 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.
-
A.
Herbrand's theorem
Herbrand's theorem is a fundamental result in mathematical logic and proof theory that characterizes the validity of first-order formulas via finite sets of ground instances, forming a basis for automated theorem proving.
-
B.
Curry–Howard correspondence
The Curry–Howard correspondence is a foundational principle in logic and computer science that establishes a deep analogy between proofs and programs, and between logical propositions and types in programming languages.
-
C.
Church–Rosser property
The Church–Rosser property is a confluence property of rewriting systems stating that if an expression can be reduced in different ways, all reduction paths can be further reduced to a common equivalent form.
-
D.
Löb's theorem
Löb's theorem is a fundamental result in mathematical logic that characterizes when a sufficiently strong formal system can prove statements about its own provability, closely refining the insights of Gödel’s incompleteness theorems.
-
E.
Gentzen’s consistency proof for arithmetic
Gentzen’s consistency proof for arithmetic is a landmark 1930s result in proof theory that established the consistency of Peano arithmetic using transfinite induction up to the ordinal ε₀.
- F. None of above. chosen
Statements (46)
| Predicate | Object |
|---|---|
| instanceOf | theorem in proof theory ⓘ |
| alsoKnownAs |
Gentzen’s Hauptsatz
ⓘ
Hauptsatz ⓘ |
| 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
ⓘ
linked to:
Gentzen-style proof systems
Gentzen’s sequent calculus LK ⓘ
linked to:
Gentzen-style proof systems
|
| 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 ⓘ
linked to:
Gentzen-style proof systems
type theory ⓘ |
| introducedBy | Gerhard Gentzen ⓘ |
| involves |
reduction of cut rank
ⓘ
reduction of proof height ⓘ |
| motivated | Gentzen’s consistency proof for arithmetic ⓘ |
| relatedTo |
Herbrand’s theorem
ⓘ
linked to:
Herbrand's theorem
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: cut-elimination theorem Description of subject: 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.
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: cut-elimination theorem