Math 2.0

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

  1. Proof theory: an overview of the field, from Hilbert's program to proof complexity.
  2. Cut rule: the rule for the use of a lemma, in its two forms.
  3. Cut-elimination theorem: Gentzen's Hauptsatz, with the mix proof and the rank-reduction proof.
  4. Subformula property: what cut-free proofs contain, and why this gives decision procedures.
  5. Normalization theorem for natural deduction: Prawitz's detour reductions and normal proofs.
  6. Midsequent theorem: the sharpened Hauptsatz for prenex sequents, and Herbrand's theorem.
  7. Inversion lemma: which rules can be read backwards without loss.
  8. Contraction-free sequent calculi: Kleene's G3 calculi and Dyckhoff's LJT.
  9. Complexity of cut elimination: the upper bound by a tower of exponentials, and a matching lower bound.
  10. Proof-theoretic semantics: meaning given by rules, harmony and tonk.
  11. Hypersequent calculus: sequents in parallel, and the communication rule.
  12. Display calculus: Belnap's display property and his general cut-elimination theorem.
  13. Labelled sequent calculus: Kripke semantics written into the rules.
  14. Deep inference: rules applied inside formulas.
  15. Focusing: proof search with phases of invertible and non-invertible rules.
  16. Identity of proofs: the open problem of when two proofs are the same.
  17. Epsilon substitution method: Hilbert's method for consistency proofs with epsilon-terms.

Prerequisites

Everything in this topic

The members of this topic and each page that they need, 187 pages in all.

  1. Alphabet concept
  2. Arity concept
  3. Beta normal form concept
  4. Beta reduction concept
  5. Binary relation concept
  6. Boolean function concept
  7. Cartesian product concept
  8. Choice function concept
  9. Completeness of atomic initial sequents concept
  10. Countermodel concept
  11. Definition by recursion concept
  12. Effectively decidable set concept
  13. Element definition
  14. Elementary recursive function concept
  15. Equivalence relation concept
  16. Exchange concept
  17. First-order variable concept
  18. Formal language concept
  19. Function concept
  20. Induction on well-formed formulas concept
  21. Intuitionistic logic concept
  22. Lambda calculus concept
  23. Linear logic concept
  24. Mathematical statement definition
  25. Multiset concept
  26. Natural numbers object
  27. Normalization property concept
  28. Peano axioms concept
  29. Power set concept
  30. Prelinearity axiom concept
  31. Proposition concept
  32. Propositional letter concept
  33. Reflexive relation concept
  34. Set concept
  35. String concept
  36. Symmetric relation concept
  37. Transitive relation concept
  38. Tuple concept
  39. Weakening concept
  40. Church–Rosser theorem statement
  41. Signature concept
  42. Set definition
  43. Logical connective definition
  44. Connectives in mathematical language concept
  45. Conjunction definition
  46. Disjunction definition
  47. Material implication definition
  48. Principle of bivalence concept
  49. Predicate concept
  50. Predicate definition
  51. Proof of Russell's paradox proof
  52. Conditional statements concept
  53. Biconditional definition
  54. Structure concept
  55. Term concept
  56. Negation concept
  57. Negation definition
  58. Atomic formula concept
  59. Truth table concept
  60. Quantifiers in mathematical writing concept
  61. Material implication concept
  62. Conjunction concept
  63. Disjunction concept
  64. Negating mathematical statements concept
  65. Tautology concept
  66. Biconditional concept
  67. Universal quantifier concept
  68. Logical connective concept
  69. Proof of the law of excluded middle by a truth table proof
  70. Logical equivalence concept
  71. Existential quantifier concept
  72. Well-formed formula concept
  73. Law of excluded middle statement
  74. Propositional calculus concept
  75. Proof of the double negation law by a truth table proof
  76. Propositional formula definition
  77. Propositional formula concept
  78. Double negation law statement
  79. First-order logic concept
  80. Free and bound variables concept
  81. Proof of unique readability by counting brackets proof
  82. Formal system concept
  83. Prenex normal form concept
  84. Substitution concept
  85. Unique readability theorem statement
  86. Natural deduction definition
  87. Hilbert's epsilon calculus concept
  88. Truth valuation concept
  89. Sequent calculus definition
  90. Harmony concept member
  91. Harmony of the conjunction rules example member
  92. The rules of tonk example member
  93. Epsilon substitution for one critical formula example member
  94. A cut-free derivation with a quantifier instance example member
  95. Cut-free LK without contraction example member
  96. Clause concept
  97. Logical consequence concept
  98. Epsilon substitution method concept member
  99. Proof-theoretic semantics concept member
  100. Epsilon substitution with nested terms example member
  101. Rule of inference concept
  102. Satisfiability concept
  103. Gentzen's consistency proof is not a substitution method example member
  104. Modus ponens concept
  105. Horn clause concept
  106. Mathematical proof concept
  107. Natural deduction concept
  108. Hilbert system concept
  109. Proof theory concept member
  110. A Hilbert-style derivation of p to p example member
  111. Proof of the deduction theorem proof
  112. Proof by contradiction concept
  113. Mathematical induction concept
  114. Sequent calculus concept
  115. Deduction theorem statement
  116. Russell's paradox statement
  117. Inductive and recursive definitions concept
  118. Linear logic definition
  119. Proof of the basic theorems of the Hilbert system L proof
  120. Cut rule definition member
  121. Cut rule concept member
  122. Contraction-free sequent calculi definition member
  123. Structural induction concept
  124. Hypersequent calculus concept member
  125. Type theory concept
  126. Basic theorems of the Hilbert system L statement
  127. Modal logic definition
  128. Proof of cut elimination by rank reduction proof member
  129. Proof of cut elimination with the mix rule proof member
  130. Contraction-free sequent calculus concept member
  131. A cut with the formula on the same side is unsound example member
  132. Chaining two implications with a cut example member
  133. The two forms of cut derive each other example member
  134. Soundness concept
  135. Proof of the inversion lemma proof member
  136. Focusing concept member
  137. Double negation of excluded middle in LJT example member
  138. Curry–Howard correspondence concept
  139. Modal logic concept
  140. Normal modal logic K definition
  141. Proof of Peirce's law proof
  142. Cut-elimination theorem statement member
  143. Inversion lemma statement member
  144. A multiplicative focused proof example member
  145. An additive focused proof example member
  146. An unfocused proof in linear logic example member
  147. Proof structure of the complexity bounds for cut elimination proof member
  148. Kripke semantics definition
  149. Simply typed lambda calculus concept
  150. Display calculus concept member
  151. Deep inference concept member
  152. Subformula property concept member
  153. Peirce's law statement
  154. Kripke semantics concept
  155. Proof of soundness of normal modal logics proof
  156. Proof of the midsequent theorem proof member
  157. Complexity of cut elimination statement member
  158. Strong normalization of simply typed lambda calculus statement
  159. Accessibility relation definition
  160. Contraction reduced to atoms by medial example member
  161. Deep inference proof of identity for a conjunction example member
  162. Switch applied inside a negation example member
  163. Implicational propositional calculus concept
  164. A cut-free derivation of Peirce's law example member
  165. Midsequent theorem statement member
  166. Peirce's law in G3cp example member
  167. Soundness of normal modal logics statement
  168. Proof of normalization for implicational natural deduction proof member
  169. Hypersequent calculus definition member
  170. Accessibility relation concept
  171. Normalization theorem for natural deduction statement member
  172. Display calculus definition member
  173. Labelled sequent calculus concept member
  174. Hypersequent calculus without the communication rule example member
  175. Hypersequent derivation of the weak excluded middle example member
  176. Labelled sequent calculus definition member
  177. Proof of the frame correspondences of the common modal axioms proof
  178. Hypersequent derivation of the prelinearity axiom example member
  179. Harmony of the implication rules example member
  180. Displaying a substructure in a display calculus example member
  181. Identity of proofs problem member
  182. Converse well-foundedness is not a geometric frame rule example member
  183. Common modal axiom schemata statement
  184. Gentzen's LK has no display property example member
  185. Display derivation of a box over a conjunction example member
  186. Labelled derivation of the axiom T example member
  187. Labelled derivation of the axiom 4 example member
About this page
TagR10RMQCJQX
URIm2://R10RMQCJQX
Kindtopic
WritingW0 stub
MSC03F03, 03F05, 03F07
Part ofMathematical logic
Changed17 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17addthe section Remarkstamnd
2026-11-17changethe section Summarytamnd

What links here

Nodes in this topic