Editing Hilbert's program (section)

==Gödel's incompleteness theorems==

{{Main|Gödel's incompleteness theorems}}

[[Kurt Gödel]] showed that most of the goals of Hilbert's program were impossible to achieve, at least if interpreted in the most obvious way. Gödel's second incompleteness theorem shows that any consistent theory powerful enough to encode addition and multiplication of integers cannot prove its own consistency. This presents a challenge to Hilbert's program:

*It is not possible to formalize '''all''' mathematical true statements within a formal system, as any attempt at such a formalism will omit some true mathematical statements. There is no complete, consistent extension of even [[Peano axioms|Peano arithmetic]] based on a [[computably enumerable]] set of axioms.
*A theory such as Peano arithmetic cannot even prove its own consistency, so a restricted "finitistic" subset of it certainly cannot prove the consistency of more powerful theories such as set theory.
*There is no algorithm to decide the truth (or provability) of statements in any consistent extension of Peano arithmetic. Strictly speaking, this negative solution to the [[Entscheidungsproblem]] appeared a few years after Gödel's theorem, because at the time the notion of an algorithm had not been precisely defined.