Gödel's Incompleteness Theorem

views updated

GÖdel's Incompleteness Theorem

By the early part of the twentieth century, the work of mathematical logicians such as Gottlob Frege, Bertrand Russell, and Alfred North Whitehead had honed the axiomatic method into an almost machine-like technique of producing mathematical theorems from carefully stated first principles (axioms) by means of clear logical rules of inference. In 1931, however, Kurt Gödel (19061978), an Austrian logician, uncovered a surprising limitation inherent in any axiomatic system intended to produce theorems expressing the familiar mathematical properties of integer arithmetic.

Gödel developed a method, whose reach was slightly extended by J. Barkley Rosser in 1936, that shows how, given any such (consistent) system of axioms, one can produce a true proposition about integers that the axiomatic system itself cannot produce as a theorem. Gödel's incompleteness result follows: Unless the axioms of arithmetic are inconsistent (self-contradictory), not all arithmetical truths can be deduced in such machine-like fashion from any fixed set of axioms. This result, that here consistency implies "incompleteness," has striking implications not only for mathematical logic, but also for machine-learning (artificial intelligence) and epistemology, although its precise significance is still debated.

Gödel's work was stimulated by a program of the mathematician David Hilbert (18621943), whose goals included showing that the consistency of higher mathematics need not be based solely upon faith in the reasonableness of its axioms and methods, but could be established using means no more questionable than those of elementary arithmetic. The link Gödel discovered between consistency and completeness of elementary arithmetic, however, led him to a further result strongly suggesting that this goal, as originally envisioned by Hilbert, is unattainable. Although relatively few nonspecialists have mastered Gödel's proof, many general readers have attained an appreciation of his argument through popular accounts of its connection with familiar paradoxes involving self-reference.

See also Artificial Intelligence; Mathematics; Paradox, Self-reference


hofstadter, douglas r. "analogies and metaphors to explain gödel's theorem." in mathematics: people, problems, results, eds. douglas m. campbell and john c. higgins. belmont, calif.: wadsworth international, 1984.

nagel, ernest, and newman, james r. gödel's proof. new york: new york university press, 1958.

w. m. priestley

About this article

Gödel's Incompleteness Theorem

Updated About encyclopedia.com content Print Article