Proof Theory — Mathematics Knowledge System

Overview

Proof theory studies formal proofs as mathematical objects. It investigates what can be proved, how efficiently, and at what logical strength. Key topics include cut elimination, ordinal analysis of theories, consistency proofs, and the relationship between proof systems and computational complexity.

Intuition

A formal proof is a finite sequence of sentences where each step follows by a fixed rule from previous steps or axioms. Proof theory asks: can you always eliminate 'detours' (cuts) from proofs? What is the minimal induction needed to prove a given theorem? How strong a logical system do you need?

Formal Definition

Definition

\Gamma \vdash \Delta

Gentzen sequent: if all of Gamma hold then some of Delta holds

sequent

\frac{\Gamma \vdash \Delta, A \quad A, \Gamma' \vdash \Delta'}{\Gamma, \Gamma' \vdash \Delta, \Delta'} \text{ (Cut)}

Cut rule: the key rule whose elimination is the main theorem

cut-rule

\text{Con}(T) \equiv \neg \text{Prov}_T(\ulcorner 0 = 1 \urcorner)

Consistency of T expressed as a formal sentence

consistency-statement

|PA|_{\leq} = \varepsilon_0 = \omega^{\omega^{\omega^{\cdots}}}

Proof-theoretic ordinal of Peano Arithmetic is epsilon-naught

proof-ordinal

Notation

Notation	Meaning
$\Gamma \vdash \Delta$	Sequent: from hypotheses Gamma derive one of Delta
$\varepsilon_0$	Epsilon-naught: least ordinal fixed point of α ↦ ωᵅ; proof-theoretic ordinal of PA
$\text{Con}(T)$	Consistency statement of theory T, formalised in arithmetic
$\text{Prov}_T$	Formal provability predicate for theory T

Theorems

Theorem 1: Gödel's First Incompleteness Theorem

Any consistent, effectively axiomatisable theory T extending PA is incomplete: there exists a sentence \varphi such that neither \varphi nor \neg\varphi is provable in T.

Theorem 2: Gödel's Second Incompleteness Theorem

Any consistent theory T extending PA cannot prove its own consistency: T \not\vdash \text{Con}(T).

Theorem 3: Gentzen's Cut Elimination

Every proof in the sequent calculus LK can be transformed into a cut-free proof. Consequently, LK is consistent and has the subformula property.

Theorem 4: Gentzen's Consistency Proof

Peano Arithmetic is consistent, provably so in a system extending PA by transfinite induction up to \varepsilon_0.

Worked Examples

Using Gödel numbering, encode all formulas as natural numbers. The provability predicate $\text{Prov}_T(n)$ is a formula of arithmetic saying 'there is a proof of the formula with Gödel number $n$'.
By the diagonal lemma (fixed-point lemma), there exists a sentence $G$ such that $PA \vdash G \leftrightarrow \neg \text{Prov}_T(\ulcorner G \urcorner)$ — $G$ asserts its own unprovability.
If $T$ proves $G$, then $T$ proves $\neg G$ (by the biconditional), contradiction. So $T \not\vdash G$. Since $T$ is consistent, $G$ is actually true (in the standard model), so $T \not\vdash \neg G$ either.

Answer: The Gödel sentence $G$ is neither provable nor disprovable in any consistent extension of PA.

Practice Problems

Difficulty 7/10

State the diagonal lemma and explain its role in Gödel's incompleteness proof.

Difficulty 8/10

Why does Gödel's second incompleteness theorem not contradict Gentzen's consistency proof of PA?

Difficulty 9/10

Prove that if $T$ is a consistent theory containing PA and $T \vdash \text{Con}(T)$, then $T$ is inconsistent — directly deriving a contradiction.

Historical Background

Hilbert launched his programme in the 1920s seeking to prove all of mathematics consistent using finitary methods. Gödel's incompleteness theorems (1931) showed this is impossible: no consistent extension of Peano arithmetic can prove its own consistency. Gentzen salvaged much of the programme by giving a consistency proof of PA using transfinite induction up to $\varepsilon_0$ in 1936. Proof theory has since evolved into ordinal analysis and connections with computer science.

1920s
Hilbert formulates his programme for finitary consistency proofs
David Hilbert
1931
Gödel's incompleteness theorems end Hilbert's programme as formulated
Kurt Gödel
1934–35
Gentzen introduces natural deduction and sequent calculus (LK)
Gerhard Gentzen
1936
Gentzen proves consistency of PA using induction up to ε₀
Gerhard Gentzen

Summary

Proof theory treats formal proofs as mathematical objects, studying their structure and limits.
Gödel's first incompleteness theorem: consistent extensions of PA are incomplete.
Gödel's second incompleteness theorem: consistent extensions of PA cannot prove their own consistency.
Gentzen's cut elimination: sequent calculus proofs can always be made cut-free.
The proof-theoretic ordinal of PA is $\varepsilon_0$; stronger theories have larger ordinals.

References

BookBuss, S. (ed.) Handbook of Proof Theory. Elsevier, 1998.
BookTroelstra, A. & Schwichtenberg, H. Basic Proof Theory. Cambridge, 2000.