- Atlas
- Mathematics
- Proof Theory
Proof Theory
Proof theory is the branch of mathematical logic that treats proofs themselves as mathematical objects.
10 frameworks, from 1920 to today · Mathematical Logic · Mathematics
- Hilbert's program 1920-1936
- Natural deduction 1934-Present
- Sequent calculus 1934-Present
- Ordinal analysis 1936-Present
- Realizability 1945-Present
- Curry–Howard correspondence 1969-Present
- Proof complexity 1975-Present
- Reverse mathematics 1975-Present
- Structural proof theory 1987-Present
- Proof mining 1990-Present
Overview
Proof theory is the branch of mathematical logic that treats proofs themselves as mathematical objects1. Where other parts of logic ask whether a statement is true in some structure, proof theory asks how a statement can be derived from axioms by explicit rules of inference—and then studies those derivations as things with shape, size, and structure1. This shift of attention, from truth to derivability, turns out to be enormously powerful. It lets logicians measure the strength of mathematical theories, extract computational content from classical arguments, and prove that certain things cannot be proved at all. Proof theory is where mathematics examines not just what is true but what can be established, and by what means.
Aristotle's syllogistic and the first proof systems
The systematic study of proof begins with Aristotle's Prior Analytics (fourth century BCE), which set out the syllogism: a form of argument in which a conclusion follows necessarily from two premises sharing a middle term. Aristotle classified valid argument forms and showed how complex arguments could be reduced to chains of syllogisms. This was the first attempt to treat reasoning as a formal object with rules, and it dominated logic for over two thousand years. The Stoics, notably Chrysippus, developed a complementary propositional logic, but Aristotle's term logic remained the canonical framework. What neither tradition had was a notion of formal proof in a precisely specified language—that would wait for the nineteenth century.
Frege, Peano, and the formalization of proof
Gottlob Frege's Begriffsschrift (1879) introduced a formal language with quantifiers and a complete set of inference rules, making it possible for the first time to write proofs in which every step could be checked mechanically against explicit rules. Frege's notation was idiosyncratic and went largely unread, but the idea was transformative. Giuseppe Peano's Arithmetices principia (1889) and, above all, Whitehead and Russell's Principia Mathematica (1910–1913) carried the project forward: mathematics was to be derived from logical axioms by formal rules. Principia made the formal derivation of mathematics a visible, laborious reality—hundreds of pages to reach basic arithmetic—and in doing so raised the question that would define proof theory: what can such formal systems prove, and what can they not?
Hilbert's programme and the birth of proof theory
David Hilbert gave proof theory its name and its founding ambition. In a series of lectures and papers around 1920, he proposed that mathematics be formalized completely, and that the consistency of the resulting formal system be established by "finitary" means—reasoning so elementary and concrete that no reasonable person could doubt it. This was Hilbert's programme: to secure classical mathematics, including its infinitary methods, by proving that the formal system encoding it could never derive a contradiction12. The program required a new discipline, which Hilbert called Beweistheorie (proof theory), devoted to the combinatorial study of formal proofs.
The programme suffered a decisive blow in 1931, when Kurt Gödel proved his incompleteness theorems: any consistent formal system strong enough to express basic arithmetic cannot prove its own consistency123. But Gödel's result did not end proof theory; it redirected it. If a system cannot prove its own consistency, one can still ask what a stronger system can prove about a weaker one, and one can still analyze the structure of proofs within a system to extract information. These two questions—consistency strength and proof structure—became the twin engines of twentieth-century proof theory.
Natural deduction and the sequent calculus
The first great technical advances came from Gerhard Gentzen, who in his 1934–1935 papers introduced two systems that remain fundamental. Natural deduction is a system of rules designed to mirror ordinary mathematical reasoning: to prove an implication, you assume the antecedent and derive the consequent; to use a disjunction, you argue by cases4. Each logical connective gets introduction and elimination rules, and a proof is a tree of formulas with assumptions at the leaves. Natural deduction made the shape of proofs an object of study and revealed deep symmetries between connectives1.
The sequent calculus was Gentzen's second system, and it proved the more powerful tool for metatheory. A sequent is an expression of the form "from assumptions A, B, C, conclude D"—written as a pair of lists separated by a turnstile. Gentzen's key result was the cut-elimination theorem (Hauptsatz): any proof in the sequent calculus can be transformed into one that never uses the cut rule, which is the formal analogue of using a previously proved lemma15. Cut-free proofs have the subformula property: every formula appearing in the proof is a subformula of the conclusion or an assumption1. This makes proof search tractable and yields consistency proofs—if the empty sequent (contradiction) had a cut-free proof, it would have to contain a formula that is a subformula of nothing, which is impossible. Gentzen used cut elimination to give the first genuine consistency proof for arithmetic (1936), though it required transfinite induction up to the ordinal ε₀, a principle not available in the system itself. This was the birth of ordinal analysis16.
Ordinal analysis: measuring the strength of theories
Ordinal analysis assigns to each formal theory a proof-theoretic ordinal—a measure of how much transfinite induction the theory can justify. Gentzen's result that arithmetic has ordinal ε₀ was the prototype6. In the decades that followed, proof theorists computed ordinals for stronger and stronger systems: predicative analysis (Feferman, Schütte, around 1960) yielded the ordinal Γ₀; impredicative systems required much larger ordinals, studied by Takeuti, Pohlers, and others from the 1960s onward. The ordinal of a theory serves as a precise calibration of its strength: if theory T has a smaller ordinal than theory S, then S proves the consistency of T. Ordinal analysis thus provides a hierarchy of mathematical theories ranked by what they can prove, and it remains one of proof theory's central enterprises.
Realizability and the computational content of proofs
A parallel development concerned what proofs compute. Stephen Kleene introduced realizability in 1945: a formula is realizable if there is a natural number (a code for a computable function) that witnesses it, in a sense defined inductively on the formula's structure. A proof of "there exists an x such that P(x)" in intuitionistic arithmetic yields, via realizability, a concrete program that produces such an x7. This made precise the intuitionistic idea—going back to Brouwer and Heyting—that a proof of an existential statement should be constructive78. Realizability became a bridge between proof theory and computability theory, and later variants (Kleene's function realizability, Kreisel's modified realizability) extended the idea to higher types and to classical systems via negative translations.
The Curry–Howard correspondence
In 1934 Haskell Curry noticed that the axioms of intuitionistic implicational logic correspond to the types of combinators in combinatory logic910. In 1969 William Alvin Howard made the correspondence explicit and general: proofs in natural deduction correspond to terms in the simply typed lambda calculus, and the formulas they prove correspond to the types of those terms. Proof normalization—the process of simplifying a proof by removing detours—corresponds exactly to term reduction in the lambda calculus. This Curry–Howard correspondence, as it came to be called, revealed that logic and computation are two views of the same structure9. It underpins modern type theory and functional programming, and it gave proof theorists a new lens: a proof is a program, and cut elimination is evaluation.
Proof mining: extracting information from classical proofs
In the 1950s and 1960s, Georg Kreisel proposed that even classical, nonconstructive proofs often contain hidden computational information that can be extracted by proof-theoretic transformations. This idea, later called proof mining, was developed into a systematic methodology by Ulrich Kohlenbach and his school from the 1990s onward. The technique uses functional interpretations and monotone variants of Gödel's Dialectica interpretation to extract bounds and rates of convergence from proofs in analysis and related fields—proofs that may rely on nonconstructive principles. Proof mining has produced new quantitative results in nonlinear analysis, fixed-point theory, and ergodic theory, showing that proof theory can contribute directly to mainstream mathematics.
Proof complexity: how hard is it to prove things?
Where ordinal analysis measures the strength of theories, proof complexity measures the difficulty of individual proofs11. Initiated by Stephen Cook and Robert Reckhow in the 1970s, the field studies how the length of the shortest proof of a formula grows with the formula's size, for various proof systems11. A central open question is whether there is a proof system in which every tautology has a polynomial-length proof—equivalent to the famous P vs. NP problem. Proof complexity has produced a rich body of results: exponential lower bounds for resolution (Haken, 1985), for cutting planes, and for many other systems, as well as connections to circuit complexity and to automated theorem proving. It is the branch of proof theory most directly concerned with efficiency rather than foundations.
Reverse mathematics: which axioms are needed?
Reverse mathematics, founded by Harvey Friedman in the 1970s and developed extensively by Stephen Simpson and others, asks a different kind of question: given a theorem of ordinary mathematics, which axioms are necessary to prove it? The program works in second-order arithmetic and has identified a small number of subsystems—RCA₀ (recursive comprehension), WKL₀ (weak König's lemma), ACA₀ (arithmetical comprehension), ATR₀ (arithmetical transfinite recursion), and Π¹₁-CA₀ (comprehension for Π¹₁ formulas)—that turn out to suffice for large swaths of classical mathematics. Most theorems of analysis, algebra, and combinatorics fall into one of these five levels, and the program has produced a detailed map of the logical strength of ordinary mathematics. Reverse mathematics is proof theory applied to the question of what mathematicians actually need to assume.
The present: structural proof theory and its neighbours
Today proof theory is a broad and active field. Structural proof theory continues to develop new calculi—linear logic (Girard, 1987), which decomposes the connectives and treats assumptions as resources; display calculi and hypersequent systems; and the proof theory of modal and substructural logics. Ordinal analysis has been extended to systems far beyond arithmetic, including subsystems of second-order arithmetic and set theory1. The Curry–Howard correspondence has grown into the field of type theory, with dependent types, homotopy type theory, and proof assistants such as Coq and Agda making formal proofs a practical tool. Proof mining continues to extract quantitative information from classical proofs in analysis12. Proof complexity remains closely tied to computational complexity theory11. And reverse mathematics has become a standard tool for calibrating the strength of theorems across mathematics. The questions that remain open are substantial: the proof-theoretic ordinals of strong impredicative systems, the existence of a proof system with polynomial-length proofs for all tautologies, and the full computational content of classical mathematics are all active frontiers. Proof theory, born from Hilbert's ambition to secure mathematics, has become the discipline that measures, extracts, and computes with the very proofs that mathematics produces.
References
- Proof theory (introduction, History, Structural proof theory, Ordinal analysis), Wikipedia
- Hilbert's program, Wikipedia
- Gödel's incompleteness theorems, Wikipedia
- Natural deduction, Wikipedia
- Cut-elimination theorem, Wikipedia
- Ordinal analysis (History), Wikipedia
- Realizability, Wikipedia
- Brouwer–Heyting–Kolmogorov interpretation, Wikipedia
- Curry–Howard correspondence (Origin, scope, and consequences, introduction), Wikipedia
- Dependent type (History), Wikipedia
- Proof complexity, Wikipedia
- Proof mining, Wikipedia
The frameworks of Proof Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1920-1936
- 1934-Present
- 1934-Present
- 1936-Present
Ordinal analysis
About Ordinal analysis
Ordinal analysis is the branch of proof theory that assigns ordinal numbers to formal systems and uses transfinite induction up to those ordinals to measure the consistency strength and proof-theoretic resources of those systems. It emerged directly from Gerhard Gentzen's response to Gödel's incompleteness theorems: if a system cannot prove its own consistency using its own methods, perhaps we can prove it consistent by appealing to a principle that is slightly stronger, yet still constructive enough to be meaningful. The central idea is to calibrate the 'strength' of a formal theory by the least ordinal needed to well-order its proofs or to carry out a consistency proof. This framework is distinct from Hilbert's Program, which sought finitary consistency proofs, and from later frameworks like Proof Mining, which extracts computational content from proofs. Ordinal analysis provides a precise, quantitative hierarchy of mathematical theories, from weak subsystems of arithmetic to strong set theories.Core CurriculumThe first course in ordinal analysis typically covers these concepts in logical order:- Ordinal numbers: The transfinite extension of the natural numbers, including limit ordinals, successor ordinals, and the first infinite ordinal . Students learn the basic arithmetic of ordinals: addition, multiplication, and exponentiation.
- Transfinite induction: The principle that if a property holds for all smaller ordinals, it holds for a given ordinal. This is the central reasoning tool in ordinal analysis.
- Cut elimination: Gentzen's Hauptsatz, which shows that any proof in the sequent calculus can be transformed into a cut-free proof. Cut-free proofs have a direct, analytic structure.
- **The ordinal **: The least fixed point of the exponential map , i.e., $\varepsilon_0 = \sup\{\omega, \omega^\omega, \omega^{\omega^\omega}, \dots\}$. This is the proof-theoretic ordinal of Peano arithmetic.
- Proof-theoretic ordinal: For a formal system , the least ordinal such that transfinite induction up to cannot be proved in , but can be used to prove 's consistency. This ordinal measures the system's strength.
- Consistency proofs via ordinal assignment: The method of assigning ordinals to proofs (or to derivations in a cut-free system) and then using transfinite induction to show that no proof can end in a contradiction.
- The ordinal analysis of Peano arithmetic: Gentzen's 1936 proof that the consistency of Peano arithmetic follows from transfinite induction up to , assuming the system itself is consistent.
- The ordinal analysis of subsystems of second-order arithmetic: Extending the method to systems like (arithmetical comprehension) and (arithmetical transfinite recursion), whose proof-theoretic ordinals are and , respectively.
- The Veblen hierarchy: A sequence of ordinal functions that extends the exponential function and generates ordinals like , the Feferman–Schütte ordinal.
- **The Feferman–Schütte ordinal **: The proof-theoretic ordinal of predicative analysis, marking the boundary of predicative mathematics.
- **The ordinal analysis of (Kripke–Platek set theory)**: A weak set theory whose proof-theoretic ordinal is the Bachmann–Howard ordinal, illustrating the extension of ordinal analysis to set theory.
- The Bachmann–Howard ordinal: A large countable ordinal used in the ordinal analysis of and related systems, defined using a collapsing function.
- Ordinal notations: Systems of terms that represent ordinals up to a certain bound, allowing them to be manipulated in a finitary way. Examples include Cantor normal form and the notation systems for and .
- The relationship to Hilbert's Program: Ordinal analysis shows that consistency proofs require principles beyond finitary reasoning, but that these principles can be calibrated and compared, providing a realization of Hilbert's goal.
Intellectual HistoryOrdinal analysis was born in 1936 when Gerhard Gentzen published his consistency proof for Peano arithmetic. Gentzen, a student of Hilbert, had already revolutionized proof theory with his sequent calculus and cut-elimination theorem (1934–1935). Gödel's incompleteness theorems (1931) had shown that no finitary consistency proof for arithmetic was possible. Gentzen's breakthrough was to use transfinite induction up to the ordinal —a principle that goes beyond finitary reasoning but is still constructive in a precise sense. His proof showed that the consistency of arithmetic could be reduced to a well-ordering principle, and that the ordinal was the exact measure of the system's strength.Gentzen's work was initially met with skepticism, partly because it used transfinite induction, which some considered non-finitary. However, his student and collaborator, Paul Bernays, helped clarify the significance of the result. Bernays, a key figure in Hilbert's Program, recognized that ordinal analysis provided a way to calibrate the strength of formal systems, even if it could not achieve Hilbert's original goal of a finitary consistency proof.In the 1940s and 1950s, the framework was extended by several logicians. Wilhelm Ackermann (1937) gave an ordinal analysis for a system of arithmetic with a restricted induction schema. In the 1950s, Kurt Schütte and Solomon Feferman independently developed the ordinal analysis of predicative systems, culminating in the identification of the Feferman–Schütte ordinal as the boundary of predicative mathematics. Schütte's work on ordinal notations and the Veblen hierarchy provided the technical tools for these analyses.Later, in the 1960s and 1970s, the framework was extended to stronger systems. Heinz Bachmann introduced the concept of collapsing functions, which allowed the definition of large countable ordinals like the Bachmann–Howard ordinal. This ordinal was used by John Steel and others in the ordinal analysis of Kripke–Platek set theory. The work of Michael Rathjen and others in the 1990s extended ordinal analysis to systems like comprehension and beyond, showing that the method could be applied to impredicative systems.Ordinal analysis coexists with later frameworks like Proof Mining (which extracts computational content from proofs) and Normalization Theory (which studies the reduction of proofs to normal form). While Proof Mining focuses on extracting programs from proofs, ordinal analysis provides the metamathematical calibration that makes such extraction possible for strong systems. The framework remains active today, with ongoing work on the ordinal analysis of set theories and the search for the proof-theoretic ordinals of systems like .Key Insights- Ordinal analysis provides a precise, quantitative measure of the strength of formal systems, allowing them to be compared and ordered by their proof-theoretic ordinals.
- It shows that consistency proofs require principles beyond the system being proved consistent, but that these principles can be systematically calibrated, offering a nuanced response to Gödel's incompleteness theorems.
- The framework bridges finitary and infinitary reasoning, showing that transfinite induction up to certain ordinals is a natural and constructive extension of finitary methods.
Common Pitfalls- A common misconception is that ordinal analysis is simply about assigning ordinals to proofs. In fact, it is about using those ordinals to prove consistency and to measure the strength of the system, not just to label proofs.
- Another pitfall is to confuse the proof-theoretic ordinal of a system with its consistency strength in a model-theoretic sense. The proof-theoretic ordinal is a syntactic measure, not a semantic one, and it is defined relative to a specific formal system and a specific notion of provability.
The 14 concepts its tower teaches
- Consistency proofs via ordinal assignment
- Cut elimination
- Ordinal notations
- Ordinal numbers
- Proof-theoretic ordinal
- The Bachmann–Howard ordinal
- The Feferman–Schütte ordinal Γ₀
- The ordinal analysis of KP (Kripke–Platek set theory)
- The ordinal analysis of Peano arithmetic
- The ordinal analysis of subsystems of second-order arithmetic
- The ordinal ε₀
- The relationship to Hilbert's Program
- The Veblen hierarchy
- Transfinite induction
- 1945-Present
- 1969-Present
- 1975-Present
- 1975-Present
- 1987-Present
- 1990-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Ordinal analysis grew out of Hilbert's program
The quest to prove the consistency of arithmetic within a formal framework necessitated the development of ordinal analysis to measure the system's strength.
Carried by Gerhard Gentzen.
Natural deduction grew out of Hilbert's program
The need to formalize mathematics consistently, driven by Hilbert's program, led to the development of natural deduction as a system mirroring intuitive reasoning.
Carried by Gerhard Gentzen.
Sequent calculus grew out of Hilbert's program
As a response to the challenges of formalization, the sequent calculus was developed to provide a more structurally amenable system for metatheoretic analysis.
Carried by Gerhard Gentzen.
Curry–Howard correspondence influenced by Natural deduction
The structure of proofs in natural deduction provided the logical foundation that Howard used to establish the correspondence between proofs and computational terms.
Proof complexity grew out of Natural deduction
The study of proof structure and complexity, building on the formal systems of deduction, led to the investigation of the inherent difficulty of finding proofs.
Ordinal analysis influenced by Sequent calculus
The cut-elimination theorem in the sequent calculus provided the necessary structural tool for Gentzen to perform the first ordinal analysis of arithmetic.
Carried by Gerhard Gentzen.
Curry–Howard correspondence influenced by Sequent calculus
The structural properties of the sequent calculus, particularly cut-elimination, provided a formal analogue for the reduction process central to the correspondence.
Structural proof theory grew out of Sequent calculus
The detailed structural analysis of proofs, pioneered by Gentzen, was refined into the systematic study of proof structure itself.
Reverse mathematics influenced by Ordinal analysis
The hierarchical classification of theories based on their proof-theoretic ordinals laid groundwork for classifying mathematical statements based on their required axiomatic strength.
Curry–Howard correspondence influenced by Realizability
Realizability provided an early, concrete model for the constructive interpretation of proofs, aligning with the computational insights of the correspondence.
Proof mining influenced by Structural proof theory
The systematic extraction of computational content from proofs required a rigorous framework for analyzing proof structure.
Beyond the field
Where Proof Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 36 links.
Hilbert's program led to Proof Theory in Mathematical Logic
Hilbert's program was the founding project of proof theory: Hilbert and his school created the discipline of metamathematics to carry out the consistency proofs the program demanded.
Carried by David Hilbert.
Natural deduction influenced Modal proof theory in Modal Logic
Modal proof theory adopted natural deduction, introduced by Gentzen and Jaśkowski, as one of its main formats for modal derivations.
Carried by Gerhard Gentzen; Stanisław Jaśkowski.
Ordinal analysis grew out of Proof Theory in Mathematical Logic
Ordinal analysis was introduced by Gentzen as the proof-theoretic method for establishing the consistency of arithmetic, and it became the central technique of proof theory after Hilbert's program.
Carried by Gerhard Gentzen.
Curry–Howard correspondence led to Proof assistant in Computational Logic
The Curry–Howard correspondence, identifying proofs with programs and propositions with types, is the theoretical foundation of type-theoretic proof assistants. Automath and later systems such as Coq and Agda are direct implementations of this correspondence.
Carried by Haskell Curry; William Alvin Howard; Nicolaas Govert de Bruijn.
Proof complexity led to Feasible Interpolation in Proof Complexity
Feasible interpolation was developed within proof complexity: Krajíček's method extracts a circuit from a proof of an interpolant, turning lower bounds on circuits into lower bounds on proof size. The proof-theoretic framework supplied the interpolation theorem and the proof systems to which the method was applied.
Carried by Jan Krajíček.
Proof complexity grew out of Computational Complexity Theory in Complexity Theory
Proof complexity is a branch of computational complexity theory, applying its notions of resource-bounded computation to proofs; the Cook-Reckhow programme defined proof systems as nondeterministic computation and asked for lower bounds in complexity terms.
Carried by Stephen A. Cook; Robert A. Reckhow.
Proof complexity grew out of Computational Complexity Theory in Theory Of Computation
Proof complexity grew directly out of computational complexity theory: Cook and Reckhow recast the P vs NP question as a question about the lengths of propositional proofs, making proof complexity a branch of complexity theory.
Carried by Stephen A. Cook; Robert A. Reckhow.
Reverse mathematics grew out of Proof Theory in Mathematical Logic
Reverse mathematics grew out of proof theory: Friedman and Simpson used proof-theoretic ordinal analysis and subsystems of second-order arithmetic to calibrate the strength of ordinary theorems.
Carried by Harvey Friedman; Stephen G. Simpson.
Structural proof theory grew out of Proof Theory in Mathematical Logic
Structural proof theory is a branch of proof theory that studies proofs as formal objects and their combinatorial structure; Gentzen's sequent calculus and natural deduction are its direct ancestors.
Carried by Gerhard Gentzen.
Proof mining grew out of Proof Theory in Mathematical Logic
Proof mining grew directly out of proof theory: it applies proof-theoretic transformations such as Herbrand and Kreisel analyses and monotone functional interpretation to extract bounds from ordinary mathematical proofs.
Carried by Ulrich Kohlenbach.
Hilbert's program reacted against Intuitionism in Foundations Of Mathematics
Hilbert's program was framed against Brouwer's intuitionism, which rejected the classical mathematics Hilbert sought to secure by finitary means; the two schools defined themselves in opposition over the 1920s.
Carried by L. E. J. Brouwer; David Hilbert.
Hilbert's program influenced Proof assistant in Formal Methods
Hilbert's programme of formalising mathematics and checking proofs by mechanical rules is the direct ancestor of the proof assistant; Automath and later systems were conceived as carrying out Hilbert's finitary proof-checking ideal with a machine.
Carried by David Hilbert; Nicolaas Govert de Bruijn.

Proof Theory is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Proof TheoryRelated fields
Fields its ideas are linked to
- Mathematical Logic 14 links
- Constructive Mathematics 3 links
- Logic 3 links
- Foundations Of Mathematics 3 links
- Philosophical Logic 2 links
- Complexity Theory 2 links
- Computational Logic 2 links
- Proof Complexity 2 links
- Modal Logic 1 link
- Philosophy Of Logic 1 link
- Mathematical Practice 1 link
- Formal Methods 1 link