Gödel's Incompleteness Theorem

Informally, Gödel's incompleteness theorem states that all consistent axiomatic formulations of Number Theory include undecidable propositions (Hofstadter 1989). This is sometimes called Gödel's first incompleteness theorem, and answers in the negative Hilbert's Problem asking whether mathematics is ``complete'' (in the sense that every statement in the language of Number Theory can be either proved or disproved). Formally, Gödel's theorem states, ``To every $\omega$-consistent recursive class $\kappa$ of Formulas, there correspond recursive class-signs $r$ such that neither ($v$ Gen $r$) nor Neg($v$ Gen $r$) belongs to Flg($\kappa$), where $v$ is the Free Variable of $r$'' (Gödel 1931).

A statement sometimes known as Gödel's second incompleteness theorem states that if Number Theory is consistent, then a proof of this fact does not exist using the methods of first-order Predicate Calculus. Stated more colloquially, any formal system that is interesting enough to formulate its own consistency can prove its own consistency Iff it is inconsistent.

Gerhard Gentzen showed that the consistency and completeness of arithmetic can be proved if ``transfinite'' induction is used. However, this approach does not allow proof of the consistency of all mathematics.

See also Gödel's Completeness Theorem, Hilbert's Problems, Kreisel Conjecture, Natural Independence Phenomenon, Number Theory, Richardson's Theorem, Undecidable

References

Barrow, J. D. Pi in the Sky: Counting, Thinking, and Being. Oxford, England: Clarendon Press, p. 121, 1992.

Gödel, K. ``Über Formal Unentscheidbare Sätze der Principia Mathematica und Verwandter Systeme, I.'' Monatshefte für Math. u. Physik 38, 173-198, 1931.

Gödel, K. On Formally Undecidable Propositions of Principia Mathematica and Related Systems. New York: Dover, 1992.

Hofstadter, D. R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, p. 17, 1989.

Kolata, G. ``Does Gödel's Theorem Matter to Mathematics?'' Science 218, 779-780, 1982.

Smullyan, R. M. Gödel's Incompleteness Theorems. New York: Oxford University Press, 1992.

Whitehead, A. N. and Russell, B. Principia Mathematica. New York: Cambridge University Press, 1927.