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 -consistent recursive class of Formulas, there correspond recursive class-signs such that neither ( Gen ) nor Neg( Gen ) belongs to Flg(), where is the Free Variable of '' (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.

**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.

© 1996-9

1999-05-25