Gödel’s Incompleteness Theorem: The Most Important Mathematical Theorem in the Twentieth Century

Below is a photo the late mathematical genius Kurt Gödel (left) with Albert Einstein. Gödel’s Incompleteness Theorem was the most important mathematical theorem in the twentieth century (its significance is explained in simple terms below). Among other things, Gödel’s theorem proves no “Theory of Everything” in physics can ever achieve the status of cetainty (this was only recently recognized by Stephen Hawking, as explained by Physicist and Philosopher of Science Stanley Jaki here.

The following material explains the mind-bending implications of this crucial theorem in simple terms, is reproduced from http://www.miskatonic.org/godel.html

From Jones and Wilson, An Incomplete Education:

“In 1931, the Czech-born mathematician Kurt Gödel demonstrated that within any given branch of mathematics, there would always be some propositions that couldn’t be proven either true or false using the rules and axioms… of that mathematical branch itself. You might be able to prove every conceivable statement about numbers within a system by going outside the system in order to come up with new rules and axioms, but by doing so you’ll only create a larger system with its own unprovable statements. The implication is that all logical system of any complexity are, by definition, incomplete; each of them contains, at any given time, more true statements than it can possibly prove according to its own defining set of rules.

“Gödel’s Theorem has been used to argue that a computer can never be as smart as a human being because the extent of its knowledge is limited by a fixed set of axioms, whereas people can discover unexpected truths… It plays a part in modern linguistic theories, which emphasize the power of language to come up with new ways to express ideas. And it has been taken to imply that you’ll never entirely understand yourself, since your mind, like any other closed system, can only be sure of what it knows about itself by relying on what it knows about itself.”

From Boyer, History of Mathematics

“Gödel showed that within a rigidly logical system such as Russell and Whitehead had developed for arithmetic, propositions can be formulated that are undecidable or undemonstrable within the axioms of the system. That is, within the system, there exist certain clear-cut statements that can neither be proved or disproved. Hence one cannot, using the usual methods, be certain that the axioms of arithmetic will not lead to contradictions … It appears to foredoom hope of mathematical certitude through use of the obvious methods. Perhaps doomed also, as a result, is the ideal of science – to devise a set of axioms from which all phenomena of the external world can be deduced.”

From Nagel and Newman, Gödel’s Proof

“He proved it impossible to establish the internal logical consistency of a very large class of deductive systems – elementary arithmetic, for example – unless one adopts principles of reasoning so complex that their internal consistency is as open to doubt as that of the systems themselves… Second main conclusion is… Gödel showed that Principia, or any other system within which arithmetic can be developed, is essentially incomplete. In other words, given any consistent set of arithmetical axioms, there are true mathematical statements that cannot be derived from the set… Even if the axioms of arithmetic are augmented by an indefinite number of other true ones, there will always be further mathematical truths that are not formally derivable from the augmented set.”

From Rucker, Infinity and the Mind

“The proof of Gödel’s Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:

1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.

2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.

3. Smiling a little, Gödel writes out the following sentence: “The machine constructed on the basis of the program P(UTM) will never say that this sentence is true.” Call this sentence G for Gödel. Note that G is equivalent to: “UTM will never say G is true.”

4. Now Gödel laughs his high laugh and asks UTM whether G is true or not.

5. If UTM says G is true, then “UTM will never say G is true” is false. If “UTM will never say G is true” is false, then G is false (since G = “UTM will never say G is true”). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.

6. We have established that UTM will never say G is true. So “UTM will never say G is true” is in fact a true statement. So G is true (since G = “UTM will never say G is true”).

7. “I know a truth that UTM can never utter,” Gödel says. “I know that G is true. UTM is not truly universal.”

Think about it – it grows on you… With his great mathematical and logical genius, Gödel was able to find a way (for any given P(UTM)) actually to write down a complicated polynomial equation that has a solution if and only if G is true. So G is not at all some vague or non-mathematical sentence. G is a specific mathematical problem that we know the answer to, even though UTM does not! So UTM does not, and cannot, embody a best and final theory of mathematics…

Although this theorem can be stated and proved in a rigorously mathematical way, what it seems to say is that rational thought can never penetrate to the final ultimate truth… But, paradoxically, to understand Gödel’s proof is to find a sort of liberation. For many logic students, the final breakthrough to full understanding of the Incompleteness Theorem is practically a conversion experience. This is partly a by-product of the potent mystique Gödel’s name carries. But, more profoundly, to understand the essentially labyrinthine nature of the castle is, somehow, to be free of it.

From Douglas Hofstadter, Gödel, Escher, and Bach

“All consistent axiomatic formulations of number theory include undecidable propositions… Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved… How can you figure out if you are sane? …Once you begin to question your own sanity, you get trapped in an ever-tighter vortex of self-fulfilling prophecies, though the process is by no means inevitable. Everyone knows that the insane interpret the world via their own peculiarly consistent logic; how can you tell if your own logic is “peculiar’ or not, given that you have only your own logic to judge itself? I don’t see any answer. I am reminded of Gödel’s second theorem, which implies that the only versions of formal number theory which assert their own consistency are inconsistent.

The other metaphorical analogue to Gödel’s Theorem which I find provocative suggests that ultimately, we cannot understand our own mind/brains… Just as we cannot see our faces with our own eyes, is it not inconceivable to expect that we cannot mirror our complete mental structures in the symbols which carry them out? All the limitative theorems of mathematics and the theory of computation suggest that once the ability to represent your own structure has reached a certain critical point, that is the kiss of death: it guarantees that you can never represent yourself totally.”

“After Gödel in any formal system there will always be true statements which cannot be proven given any finite set of assumptions. How to demarcate statements that are not provable but true from statements that are not provable because they are not true is unresolved in any such system.” -B. David Hemlock

“The intrinsic merits of the goal of devising an ultimate physical theory should also seem nil as long as the theory is sufficiently mathematical, which such a theory certainly has to be. Now Gödel’s incompleteness theorem states that the proof of consistency of any non-trivial set of mathematical axioms can be only found outside that set, and in that sense no mathematical system can be an ultimate system. In other words, whereas General Relativity forces us to admit the realistic character of the notion of consistently interacting things, as a valid object of scientific cosmology, the application of Gödel’s theorem to cosmology shows that a disproof of the contingency of the universe is impossible. The mental road to the extracosmic Absolute remains therefore fully open.” –Stanley Jaki, “The Absolute Beneath the Relative,” The Intercollegiate Review, 1985

“…quantitative proofs rest on our ability to count and to do arithmetic in a consistent way. As consistency presupposes laws, counting too makes sense only if it is done according to some laws of arithmetic. Depending on the extensiveness of the arithmetic one uses, its laws too form a more or less extensive set. This set also must have its proof of consistency or else 2 and 2 will not always and necessarily make 4 and the whole enterprise will collapse. In 1930, Gödel proved that no sufficiently broad set of laws of arithmetic can have its proof of consistency within itself. To have the proof, one must reach out for assumptions lying outside the set and to prove the consistency of these assumptions, one must rely on still further assumptions. This means that to prove the consistency of quantitative science one must rely on considerations which the prevailing jargon calls metaquantitative or metamathematical. In older times, when there was till more courage to call a spade a spade, one would have said not metamathematical but metaphysical. –Stanley Jaki, “The Absolute Beneath the Relative,” The Intercollegiate Review, 1985

 

Advertisements
This entry was posted in Science and Philosophy, Uncategorized. Bookmark the permalink.

One Response to Gödel’s Incompleteness Theorem: The Most Important Mathematical Theorem in the Twentieth Century

  1. Pingback: POEM: Wading for Gödel

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s