Simple tasks must be simple, and complex ones must be possible.
--Alan Kay

  Godel Incompleteness Theorem

Central | Recent Changes | The Network | Talk unknown user

Gödel's Incompleteness Theorem

At a 1928 international mathematical congress, the German logician David Hilbert formally presented three questions: Is mathematics complete, consistent, and decidable? (Alternately: every mathematical question be solvable in principle; every result be checkable; every mathematical question be decidable in a finite number of steps.) A mathematical theory (or system) consists of true and false statements, provable from a set of axioms; if all true statements are provable, the theory is complete; if it is not possible to prove a statement and its negation, the theory is consistent; if the theory includes a mechanism for separating all provable statements from unprovable ones, the theory is decidable. An inconsistent theory is trivially complete, because all statements, true or false, are provable.

With the usual confidence of his age, Hilbert expected the answer to all three questions to be yes. He believed that the essential structure of mathematics did not contain paradox, though humankind had not yet discovered such structure.

At the very same congress, young Kurt Gödel introduced his proof, now known as Gödelís Incompleteness Theorem, that mathematics is not complete. He made the radical realization that because all mathematics is composed of symbols, the objects of mathematics (such as numbers) are inextricable from the structure of mathematics (such as truth and proofs), making paradoxes unavoidable.

Previous mathematicians and logicians showed that all mathematics can be wholly composed of statements about symbols. All the mathematics of geometry, which seems to depend on diagrams of lines and curves, can be expressed fully in a series of mathematical statements, no different from algebra or logic. Which symbols are chosen makes no difference. You can do the same math by writing 1+1=2 or 1gibble1gobble2, as long as "gibble" and "gobble" are defined to mean the same thing as + and =, respectively.

Using Gödel numbers, he was able to essentially show that the statement "This statement is unprovable" can be constructed in any robust mathematical system.

More specifically, the statement is "There is no GŲdel number which encodes a proof of this statement." The statement must be either true or false. If it is false, that means a proof of the statement exists, which means that false statements in the system are provable, which we certainly donít want. So the statement must be true. Any proof must be able to be written in a finite number of steps, so all proofs are encodable as GŲdel numbers. Therefore the statement isnít provable.

Since that statement canít be proven or disproven, any mathematical system that allows it canít be complete. GŲdelís proof involved a profound realization about the nature of information: In a closed, self-defined system, there is no distinction between number and symbol, object and structure, meaning and data. Only by stepping outside the system can one say that anything is true or false in any meaningful way. And if you speak only in the language of the system you are bound by its rules, the very rules that guarantee incompleteness.

As knowledge of Gödelís work spread, people began applying the incompleteness theorem in unusual ways. Some mathematicians found it cause for despair; others regarded it optimistically, embracing the near-mystical uncertainty of whether or not certain theorems were indeed provable. Some asserted that it was a proof of Godís existence or the magic of human intellect and consciousness. There are limitations on logic and mathematics, they said, but human emotion and thought are unbounded.

Central | Recent Changes | The Network | Talk unknown user
unknown userRSS