Gödel's First Incompleteness Theorem

Gödel's first incompleteness theorem states that all consistent axiomatic formulations of number theory which include Peano arithmetic include undecidable propositions (Hofstadter 1989). This 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).

The inclusion of Peano arithmetic is needed, since for example Presburger arithmetic is a consistent axiomatic formulation of number theory, but it is decidable.

However, Gödel's first incompleteness theorem also holds for Robinson arithmetic (though Robinson's result came much later and was proved by Robinson).

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, 1993.

Erickson, G. W. and Fossa, J. A. Dictionary of Paradox. Lanham, MD: University Press of America, pp. 74-75, 1998.

Franzén, T. "Gödel on the Net." http://www.sm.luth.se/~torkel/eget/godel.html.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.

Rucker, R. Infinity and the Mind: The Science and Philosophy of the Infinite. Princeton, NJ: Princeton University Press, 1995.

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.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 782, 2002.