Editing Gödel's incompleteness theorems (section)

{{Short description|Limitative results in mathematical logic}}
{{pp-pc}}
{{For|the earlier theory about the correspondence between truth and provability|Gödel's completeness theorem}}

'''Gödel's incompleteness theorems''' are two [[theorem]]s of [[mathematical logic]] that are concerned with the limits of {{not a typo|provability}} in formal axiomatic theories. These results, published by [[Kurt Gödel]] in 1931, are important both in mathematical logic and in the [[philosophy of mathematics]]. The theorems are widely, but not universally, interpreted as showing that [[Hilbert's program]] to find a complete and consistent set of [[axiom]]s for all [[mathematics]] is impossible.<ref>{{cite book | isbn=0-465-02656-7 | author=Douglas Hofstadter | title=Gödel, Escher, Bach: an Eternal Golden Braid | location=New York | publisher=Basic Books | year=1979 }} Here: ''Introduction'' / ''Consistency, completeness, Hilbert's program''; "Gödel published his work which in some sense completely destroyed Hilbert's program."</ref>{{additional citation needed|date=May 2025|reason=At least provide another citation, supporting "not universally".}}

The first incompleteness theorem states that no [[consistency|consistent system]] of [[axiom]]s whose theorems can be listed by an [[effective procedure]] (i.e. an [[algorithm]]) is capable of [[Mathematical proof|proving]] all truths about the arithmetic of [[natural number]]s.  For any such consistent formal system, there will always be statements about natural numbers that are true, but that are unprovable within the system.

The second incompleteness theorem, an extension of the first, shows that the system cannot demonstrate its own consistency.

Employing a [[Cantor's diagonal argument|diagonal argument]], Gödel's incompleteness theorems were among the first of several closely related theorems on the limitations of formal systems. They were followed by [[Tarski's undefinability theorem]] on the formal undefinability of truth, [[Alonzo Church|Church]]'s proof that Hilbert's ''[[Entscheidungsproblem]]'' is unsolvable, and [[Alan Turing|Turing]]'s theorem that there is no algorithm to solve the [[halting problem]].