Areas Mathematical logic Topic
Structural proof theory
Summary
This topic is a part of mathematical logic. It covers formal proofs as combinatorial objects: cut elimination, normalization, the subformula property, refined sequent systems and proof-theoretic semantics. The sub-area studies how proofs can be transformed, which normal forms they have, and what these normal forms show about the logic.
Remarks
Reading order
- Proof theory: an overview of the field, from Hilbert's program to proof complexity.
- Cut rule: the rule for the use of a lemma, in its two forms.
- Cut-elimination theorem: Gentzen's Hauptsatz, with the mix proof and the rank-reduction proof.
- Subformula property: what cut-free proofs contain, and why this gives decision procedures.
- Normalization theorem for natural deduction: Prawitz's detour reductions and normal proofs.
- Midsequent theorem: the sharpened Hauptsatz for prenex sequents, and Herbrand's theorem.
- Inversion lemma: which rules can be read backwards without loss.
- Contraction-free sequent calculi: Kleene's G3 calculi and Dyckhoff's LJT.
- Complexity of cut elimination: the upper bound by a tower of exponentials, and a matching lower bound.
- Proof-theoretic semantics: meaning given by rules, harmony and tonk.
- Hypersequent calculus: sequents in parallel, and the communication rule.
- Display calculus: Belnap's display property and his general cut-elimination theorem.
- Labelled sequent calculus: Kripke semantics written into the rules.
- Deep inference: rules applied inside formulas.
- Focusing: proof search with phases of invertible and non-invertible rules.
- Identity of proofs: the open problem of when two proofs are the same.
- Epsilon substitution method: Hilbert's method for consistency proofs with epsilon-terms.
Prerequisites
- Proof systems for first-order logic, with the sequent calculus LK and LJ and natural deduction.
- The propositional calculus and first-order languages and syntax, for formulas, substitution and subformulas.
- Structures, satisfaction and truth, for the soundness arguments.
Everything in this topic
The members of this topic and each page that they need, 187 pages in all.
- Alphabet concept
- Arity concept
- Beta normal form concept
- Beta reduction concept
- Binary relation concept
- Boolean function concept
- Cartesian product concept
- Choice function concept
- Completeness of atomic initial sequents concept
- Countermodel concept
- Definition by recursion concept
- Effectively decidable set concept
- Element definition
- Elementary recursive function concept
- Equivalence relation concept
- Exchange concept
- First-order variable concept
- Formal language concept
- Function concept
- Induction on well-formed formulas concept
- Intuitionistic logic concept
- Lambda calculus concept
- Linear logic concept
- Mathematical statement definition
- Multiset concept
- Natural numbers object
- Normalization property concept
- Peano axioms concept
- Power set concept
- Prelinearity axiom concept
- Proposition concept
- Propositional letter concept
- Reflexive relation concept
- Set concept
- String concept
- Symmetric relation concept
- Transitive relation concept
- Tuple concept
- Weakening concept
- Church–Rosser theorem statement
- Signature concept
- Set definition
- Logical connective definition
- Connectives in mathematical language concept
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- Predicate concept
- Predicate definition
- Proof of Russell's paradox proof
- Conditional statements concept
- Biconditional definition
- Structure concept
- Term concept
- Negation concept
- Negation definition
- Atomic formula concept
- Truth table concept
- Quantifiers in mathematical writing concept
- Material implication concept
- Conjunction concept
- Disjunction concept
- Negating mathematical statements concept
- Tautology concept
- Biconditional concept
- Universal quantifier concept
- Logical connective concept
- Proof of the law of excluded middle by a truth table proof
- Logical equivalence concept
- Existential quantifier concept
- Well-formed formula concept
- Law of excluded middle statement
- Propositional calculus concept
- Proof of the double negation law by a truth table proof
- Propositional formula definition
- Propositional formula concept
- Double negation law statement
- First-order logic concept
- Free and bound variables concept
- Proof of unique readability by counting brackets proof
- Formal system concept
- Prenex normal form concept
- Substitution concept
- Unique readability theorem statement
- Natural deduction definition
- Hilbert's epsilon calculus concept
- Truth valuation concept
- Sequent calculus definition
- Harmony concept member
- Harmony of the conjunction rules example member
- The rules of tonk example member
- Epsilon substitution for one critical formula example member
- A cut-free derivation with a quantifier instance example member
- Cut-free LK without contraction example member
- Clause concept
- Logical consequence concept
- Epsilon substitution method concept member
- Proof-theoretic semantics concept member
- Epsilon substitution with nested terms example member
- Rule of inference concept
- Satisfiability concept
- Gentzen's consistency proof is not a substitution method example member
- Modus ponens concept
- Horn clause concept
- Mathematical proof concept
- Natural deduction concept
- Hilbert system concept
- Proof theory concept member
- A Hilbert-style derivation of p to p example member
- Proof of the deduction theorem proof
- Proof by contradiction concept
- Mathematical induction concept
- Sequent calculus concept
- Deduction theorem statement
- Russell's paradox statement
- Inductive and recursive definitions concept
- Linear logic definition
- Proof of the basic theorems of the Hilbert system L proof
- Cut rule definition member
- Cut rule concept member
- Contraction-free sequent calculi definition member
- Structural induction concept
- Hypersequent calculus concept member
- Type theory concept
- Basic theorems of the Hilbert system L statement
- Modal logic definition
- Proof of cut elimination by rank reduction proof member
- Proof of cut elimination with the mix rule proof member
- Contraction-free sequent calculus concept member
- A cut with the formula on the same side is unsound example member
- Chaining two implications with a cut example member
- The two forms of cut derive each other example member
- Soundness concept
- Proof of the inversion lemma proof member
- Focusing concept member
- Double negation of excluded middle in LJT example member
- Curry–Howard correspondence concept
- Modal logic concept
- Normal modal logic K definition
- Proof of Peirce's law proof
- Cut-elimination theorem statement member
- Inversion lemma statement member
- A multiplicative focused proof example member
- An additive focused proof example member
- An unfocused proof in linear logic example member
- Proof structure of the complexity bounds for cut elimination proof member
- Kripke semantics definition
- Simply typed lambda calculus concept
- Display calculus concept member
- Deep inference concept member
- Subformula property concept member
- Peirce's law statement
- Kripke semantics concept
- Proof of soundness of normal modal logics proof
- Proof of the midsequent theorem proof member
- Complexity of cut elimination statement member
- Strong normalization of simply typed lambda calculus statement
- Accessibility relation definition
- Contraction reduced to atoms by medial example member
- Deep inference proof of identity for a conjunction example member
- Switch applied inside a negation example member
- Implicational propositional calculus concept
- A cut-free derivation of Peirce's law example member
- Midsequent theorem statement member
- Peirce's law in G3cp example member
- Soundness of normal modal logics statement
- Proof of normalization for implicational natural deduction proof member
- Hypersequent calculus definition member
- Accessibility relation concept
- Normalization theorem for natural deduction statement member
- Display calculus definition member
- Labelled sequent calculus concept member
- Hypersequent calculus without the communication rule example member
- Hypersequent derivation of the weak excluded middle example member
- Labelled sequent calculus definition member
- Proof of the frame correspondences of the common modal axioms proof
- Hypersequent derivation of the prelinearity axiom example member
- Harmony of the implication rules example member
- Displaying a substructure in a display calculus example member
- Identity of proofs problem member
- Converse well-foundedness is not a geometric frame rule example member
- Common modal axiom schemata statement
- Gentzen's LK has no display property example member
- Display derivation of a box over a conjunction example member
- Labelled derivation of the axiom T example member
- Labelled derivation of the axiom 4 example member
About this page
| Tag | R10RMQCJQX |
|---|---|
| URI | m2://R10RMQCJQX |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03F03, 03F05, 03F07 |
| Part of | Mathematical logic |
| Changed | 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | add | the section Remarks | tamnd |
| 2026-11-17 | change | the section Summary | tamnd |
What links here
Nodes in this topic
- Midsequent theorem
- Display calculus
- Labelled derivation of the axiom 4
- The two forms of cut derive each other
- Display calculus
- A multiplicative focused proof
- Hypersequent calculus
- Deep inference
- Harmony of the conjunction rules
- Display derivation of a box over a conjunction
- Hypersequent calculus
- Contraction reduced to atoms by medial
- Epsilon substitution for one critical formula
- Hypersequent calculus without the communication rule
- Displaying a substructure in a display calculus
- A cut-free derivation with a quantifier instance
- Proof of cut elimination with the mix rule
- Focusing
- Proof of the inversion lemma
- Cut-elimination theorem
- Complexity of cut elimination
- Hypersequent derivation of the prelinearity axiom
- Contraction-free sequent calculus
- An unfocused proof in linear logic
- Switch applied inside a negation
- A Hilbert-style derivation of p to p
- Cut rule
- Inversion lemma
- Labelled sequent calculus
- Epsilon substitution method
- Proof structure of the complexity bounds for cut elimination
- Identity of proofs
- Epsilon substitution with nested terms
- A cut with the formula on the same side is unsound
- Labelled derivation of the axiom T
- Cut rule
- Gentzen's consistency proof is not a substitution method
- Proof of the midsequent theorem
- Chaining two implications with a cut
- The rules of tonk
- Proof-theoretic semantics
- Contraction-free sequent calculi
- Deep inference proof of identity for a conjunction
- Cut-free LK without contraction
- Peirce's law in G3cp
- Proof theory
- Proof of cut elimination by rank reduction
- Hypersequent derivation of the weak excluded middle
- Converse well-foundedness is not a geometric frame rule
- Harmony of the implication rules
- An additive focused proof
- Gentzen's LK has no display property
- Double negation of excluded middle in LJT
- Labelled sequent calculus
- Normalization theorem for natural deduction
- A cut-free derivation of Peirce's law
- Harmony
- Subformula property
- Proof of normalization for implicational natural deduction