Gentzen's consistency proof

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction (i.e. are "consistent"), as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε₀", is neither weaker nor stronger than the system of Peano axioms. Gentzen argued that it avoids the questionable modes of inference contained in Peano arithmetic and that its consistency is therefore less controversial.

Gentzen's theorem

Gentzen theorem is concerned with first-order arithmetic: the theory of the natural numbers, including their addition and multiplication, axiomized by the Peano axioms. This is a "first-order" theory: the quantifiers extend over natural numbers, but not over sets or functions of natural numbers. The theory is strong enough to describe recursively defined integer functions such as exponentiation, factorials or the Fibonacci sequence.

Gentzen showed that the consistency of the first-order Peano axioms is provable, over the base theory of primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε₀. Primitive recursive arithmetic is a much simplified form of arithmetic which is rather uncontroversial. The additional principle means, informally, that there is a well-ordering on the set of finite rooted trees. Formally, ε₀ is the first ordinal $\alpha$ such that $\omega ^{\alpha }=\alpha$, i.e. the limit of the sequence:

$\omega,\ \omega^\omega,\ \omega^{\omega^\omega},\ \ldots$

To express ordinals in the language of arithmetic, an ordinal notation is needed, i.e. a way to assign natural numbers to ordinals less than ε₀. This can be done in various ways, one example provided by Cantor's normal form theorem. We require for any quantifier-free formula A(x): if there is an ordinal x< ε₀ for which A(x) is false, then there is a least such ordinal.

Gentzen defines a notion of "reduction procedure" for proofs in Peano arithmetic. For a given proof, such a procedure produces a tree of proofs, with the given one serving as the root of the tree, and the other proofs being, in a sense, "simpler" than the given one. This increasing simplicity is formalized by attaching an ordinal < ε₀ to every proof, and showing that, as one moves down the tree, these ordinals get smaller with every step. He then shows that if there were a proof of a contradiction, the reduction procedure would result in an infinite descending sequence of ordinals smaller than ε₀ produced by a primitive recursive operation on proofs corresponding to a quantifier-free formula.^[1]

It is possible to interpret Gentzen's proof in game-theoretic terms (Tait 2005).

Relation to Hilbert's program and Gödel's theorem

Gentzen's proof highlights one commonly missed aspect of Gödel's second incompleteness theorem. It is sometimes claimed that the consistency of a theory can only be proved in a stronger theory. The theory obtained by adding quantifier-free transfinite induction to primitive recursive arithmetic proves the consistency of first-order arithmetic but is not stronger than first-order arithmetic. For example, it does not prove ordinary mathematical induction for all formulae, while first-order arithmetic does (it has this as an axiom schema). The resulting theory is not weaker than first-order arithmetic either, since it can prove a number-theoretical fact – the consistency of first-order arithmetic – that first-order arithmetic cannot. Therefore the two theories are incomparable.

Hermann Weyl made the following comment in 1946 regarding the significance of Gentzen's consistency result following the devastating impact of Gödel's 1931 incompleteness result on Hilbert's plan to prove the consistency of mathematics.^[2]

It is likely that all mathematicians ultimately would have accepted Hilbert's approach had he been able to carry it out successfully. The first steps were inspiring and promising. But then Gödel dealt it a terrific blow (1931), from which it has not yet recovered. Gödel enumerated the symbols, formulas, and sequences of formulas in Hilbert's formalism in a certain way, and thus transformed the assertion of consistency into an arithmetic proposition. He could show that this proposition can neither be proved nor disproved within the formalism. This can mean only two things: either the reasoning by which a proof of consistency is given must contain some argument that has no formal counterpart within the system, i.e., we have not succeeded in completely formalizing the procedure of mathematical induction; or hope for a strictly "finitistic" proof of consistency must be given up altogether. When G. Gentzen finally succeeded in proving the consistency of arithmetic he trespassed those limits indeed by claiming as evident a type of reasoning that penetrates into Cantor's "second class of ordinal numbers."

Kleene (2009, p. 479) made the following comment in 1952 on the significance of Gentzen's result, particularly in the context of the formalist program which was initiated by Hilbert.

The original proposals of the formalists to make classical mathematics secure by a consistency proof did not contemplate that such a method as transfinite induction up to ε₀ would have to be used. To what extent the Gentzen proof can be accepted as securing classical number theory in the sense of that problem formulation is in the present state of affairs a matter for individual judgement, depending on how ready one is to accept induction up to ε₀ as a finitary method.

Other consistency proofs of arithmetic

Gentzen's first version of his consistency proof was not published during his lifetime because Paul Bernays had objected to a method implicitly used in the proof. The modified proof, described above, was published in 1936 in the Annals. Gentzen went on to publish two more consistency proofs, one in 1938 and one in 1943. All of these are contained in (Gentzen & Szabo 1969).

In 1940 Wilhelm Ackermann published another consistency proof for Peano arithmetic, also using the ordinal ε₀.

Work initiated by Gentzen's proof

Gentzen's proof is the first example of what is called proof-theoretical ordinal analysis. In ordinal analysis one gauges the strength of theories by measuring how large the (constructive) ordinals are that can be proven to be well-ordered, or equivalently for how large a (constructive) ordinal can transfinite induction be proven. A constructive ordinal is the order type of a recursive well-ordering of natural numbers.

Laurence Kirby and Jeff Paris proved in 1982 that Goodstein's theorem cannot be proven in Peano arithmetic based on Gentzen's theorem.

Notes

1. See Kleene (2009, pp. 476–499) for a full presentation of Gentzen's proof and various comments on the historic and philosophical significance of the result.
2. Weyl (2012, p. 144).

References

• Gentzen, Gerhard (1936), "Die Widerspruchsfreiheit der reinen Zahlentheorie", Mathematische Annalen, 112: 493–565, doi:10.1007/BF01565428 - Translated as 'The consistency of arithmetic', in (Gentzen & Szabo 1969).
• Gentzen, Gerhard (1938), "Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie", Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, 4: 19–44 - Translated as 'New version of the consistency proof for elementary number theory', in (Gentzen & Szabo 1969).
• Gentzen, Gerhard (1969), M. E., Szabo, ed., Collected Papers of Gerhard Gentzen, Studies in logic and the foundations of mathematics (Hardcover ed.), Amsterdam: North-Holland, ISBN 0-7204-2254-X - an English translation of papers.
• Gödel, K. (2001) [1938], "Lecture at Zilsel's", in Feferman, Solomon, Kurt Gödel: Collected Works, vol.III Unpublished Essays and Lectures (Paperback ed.), Oxford University Press Inc., pp. 87–113, ISBN 0-19-514722-7
• Jervell, Herman Ruge (1999), A course in proof theory (textbook draft ed.)
• Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic" (PDF), Bull. London Math. Soc., LMS, 14: 285–293, doi:10.1112/blms/14.4.285
• Kleene, Stephen Cole (2009) [1952]. Introduction to metamathematics. Ishi Press International. ISBN 978-0-923891-57-2.
• Tait, W. W. (2005), "Gödel's reformulation of Gentzen's first consistency proof for arithmetic: the no-counterexample interpretation" (PDF), The Bulletin of Symbolic Logic, ASL, 11 (2): 225–238, doi:10.2178/bsl/1120231632, ISSN 1079-8986
• Weyl, Hermann (2012). Levels of infinity: Selected writings on mathematics and philosophy. New York: Dover Publications. ISBN 978-0-486-48903-2.