Editing Hilbert's second problem (section)

== Gentzen's consistency proof ==

{{main|Gentzen's consistency proof}}

In 1936, Gentzen published a proof that Peano Arithmetic is consistent. Gentzen's result shows that a consistency proof can be obtained in a system that is much weaker than set theory.

Gentzen's proof proceeds by assigning to each proof in Peano arithmetic an [[ordinal number]], based on the structure of the proof, with each of these ordinals less than [[epsilon numbers (mathematics)|ε<sub>0</sub>]].<ref>Actually, the proof assigns a "notation" for an ordinal number to each proof.  The notation is a finite string of symbols that intuitively stands for an ordinal number.  By representing the ordinal in a finite way, Gentzen's proof does not presuppose strong axioms regarding ordinal numbers.</ref> He then proves by [[transfinite induction]] on these ordinals that no proof can conclude in a contradiction.  The method used in this proof can also be used to prove a [[cut elimination]] result for [[Peano arithmetic]] in a stronger logic than first-order logic, but the consistency proof itself can be carried out in ordinary first-order logic using the axioms of [[primitive recursive arithmetic]] and a transfinite induction principle. {{harvtxt|Tait|2005}} gives a game-theoretic interpretation of Gentzen's method.

Gentzen's consistency proof initiated the program of [[ordinal analysis]] in proof theory.  In this program, formal theories of arithmetic or set theory are assigned [[ordinal numbers]] that measure the [[consistency strength]] of the theories. A theory will be unable to prove the consistency of another theory with a higher proof theoretic ordinal.