proving Gödel
Sunday, April 13th, 2008The implications of Gödel’s Theorem are profound. A full understanding of its implications is not restricted to math professionals, however - there are numerous books that have addressed Gödel, aimed at a layman audience. Of these the most famous is Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter. That’s a book that every geek needs to have on their bookshelf. However, there are many more, and short excerpts from many of these books on the topic of Gödel have been compiled in one place.
The most powerful explanation of Gödel is to simply restate it’s proof in general terms. That proof, originally published in Infinity and the Mind by Rudy Rucker, is reproduced below (courtesy of Miskatonic.org).
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.”
As Rucker says, think about that a bit. It grows on you. Rucker goes on to explain,
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.
The castle to which he refers is Reason itself.
Or, as The Hoft put it:
Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved.
(for more on the limitations of reason, and the false promise of what Hofstadter called “super-rationality”, see Super-Rational blog.)
