Kurt Godel

The Undecidable Man

Without doubt Kurt Godel's big claim to fame were his "undecidability" theorems (there are actually two of them) about how some mathematical statements have no proof, but are nonetheless true. Sci-fi fans, on the other hand, might prefer his equations where the universe rotates in time. What you have then is a cosmology where the future eventually returns to the past. How about that! Kurt proved time travel is possible!

Alas, others, a bit more mundane, simply point out that this "forward to the past" universe is only one solution to the equation, and it may have no real meaning. In fact, there is another solution to Kurt's cosmology where time proceeds forward normally, and the universe physically rotates back to it's origin. That's probably the more meaningful solution.

But it's Kurt's undecidability theorems that really caught the public's imagination (or for the minority of the public who even knows who Kurt is). Kurt, we learn, proved with mathematical rigor that there are true statements that can't be proven. Naturally such a finding can be (and has been) seized with glee by the various agenda wielders to "prove" why their own pet philosophical systems like Bible and the United States Constitution are true but not subject to logical proof. Too bad this type of "truth without proof" is not what Kurt proved at all.

What Kurt did was prove that if you have a mathematical system as "rich" as that of the Principia Mathematica - the massive three volume development of number theory written by Alfred North Whitehead and Bertrand Russell - you can construct well-formed formulas (a fancy word for mathematical expressions) that cannot be proven within the system. Bertie, we should point out, although (or perhaps because) he was one of the greatest mathematicians of the late nineteenth and early twentieth century, had no illusions of the great philosophical teachings of numbers. Mathematics, he said, was a field where you never know what you're talking about or what you are saying is true. All the "profound" truths of math, he added, are like coming to the astounding conclusion that there are no seventy year old octogenarians.

Kurt's first paper is available in a cheap English paperback translation. But it's is pretty hard going. Instead the interested might try the small book "Godel's Proof" by James Newman and Ernest Nagel (New York University Press, 2002). This goes in enough detail so you can see what Kurt did. Once you've done with James' and Ernest's book, and have a good mathematical background, you can start reading Kurt's paper. But don't start at the beginning, but at the definitions, and it's easy enough to see where and how Kurt is heading.

What Kurt did was demonstrate with you can rank all mathematical expressions which can crafted by the rules of a system into a list. Therefore each expression has a unique number assigned to it. Then he showed that somewhere, some place, there is a formula that states "Theorem #N is not provable". The odd thing is the number of "Theorem #N is not provable" just happens to be N itself! The statement (ergo, the theorem) asserts its on non-provability. So if the theorem is true, it's not provable and if it's not true, you can prove a false statement - which means your system is inconsistent and worthless.

But if you reason outside the system, you come to a surprising conclusion. That is, we just reasoned that if the theorem can be proven then your system allows you to prove false statements. This is the definition of an inconsistent system. On the other hand if our system that created the formula is consistent, then we can't prove it. But hold on! That's exactly what the statement says! So by thinking "outside the system", we just proved the statement was true. For a bit more detail about Kurt's theorem, just click here.

At this point you may find yourself scratching your head and wondering if Kurt's trying to pull a fast one. Or at least wondering if the theorem is really what it's cracked up to be. After all what use is a mathematical (or logical) expression that simply asserts it can't be proven? At this point we need to point out there seems to be a bit of a schism between philosophers and logicians with the mathematicians. Although no knowledgeable expert questions the technical correctness of Kurt's proof, the hard nosed mathematicians will point out that Godel's theorem really didn't change the study of mathematics as much as people think. In fact, it changed it very little.

What Kurt proved, one mathematics professor has pointed out, was if you use a sufficiently broad definition for the word "number", then there are indeed formulas that are true but have no formal proof. But these proofs are not of much interest to most mathematicians anyway. So even if there are regions of the field for mathematicians to avoid, as Kurt warns, few would ever drift into those regions anyway. As it is, most mathematicians, even those working in fundamental research, proceed through their careers without scarce a glance at what Kurt did, thank you.

So was Kurt one of the most fundamental and profound thinkers of the 20th century, or are his theorems correct but overrated? That's probably a matter of opinion, more than anything else, although Stanislaw Ulam, the Polish mathematician, thought Kurt worried about that himself. Instead Stanislaw, who knew Kurt well, believed that Kurt was afraid that when you got down to it, he might had done nothing more than come up with a complex form of the amusing logical paradoxes like when Epimenides, the Cretan, said "All Cretans are liars".

Still every now and then someone asks if one of the unsolved problems of mathematics - like Collatz's Conjecture (often incorrectly called Ulam's Conjecture - is a formula that can't be proven within the system. Even though some real mathematical formulas have been show to be undecidable, there are others that were once suspected to be Godel Unprovable - like Fermat's Last Theorem - have indeed been proven.

After Kurt it became quite chic to prove the non-provable. Mathematician and early computer scientist Alan Turing demonstrated that there's no point in trying to program a computer that will automatically solve everything. It can't be done. And for the curious, there are fairly simple proofs that true mathematical statements exist but which have no proof. You can read one of the bonehead examples in a new window as part of another essay by clicking here. Alan's proof - which is reasonably easy to understand is here

Today you even find people pooh-poohing Kurt's work, saying it's obvious. Euclid, we hear, knew there were undecidable mathematical statements - like his Fifth Postulate - that are true or false depending on the particular system. And there are those that snort that it's obvious there are uncountably infinite truths and only countably infinite theorems is obvious if you understand Cantor's diagonal argument that we just mentioned above. Of course, it's easy to say something is obvious once it's been pointed out - every bit easy making a - quote - "prophecy" - unquote - after the event has already happened. That, of course, is what keeps the mystics and occultists in business.

Kurt himself, though, had a mystical streak. Using modal logic, a logic that includes the concept of necessity and possibility, he worked out a proof for the existence of God. The proof is quite short and not particularly difficult to understand. But Kurt's proof does require some new and not quite self evident axioms, and Kurt also had to invent a completely new property for God (and everyone else who had it) called positivity. Once more empiricists snort that all this is simply reverse engineering. Find the answer you want, and work backwards until you come up with a system and axioms which are not self evident (and possibly nonsensical) that give you what you're trying to prove.

Or perhaps Kurt once more is proving that if you use a sufficiently broad definition of God, then you can, indeed, prove he (or she) exists. (For CooperToons version of such an "ontological" proof, click here ). But the sad truth is such "proofs by definition" are almost always trivial, and what Kurt proved has absolutely nothing to do with whether the God of any of the currently practiced world religions really exits. For which we can thank God.

Kurt was born in what is now the Czech Republic and grew up in Vienna. Finding himself a citizen of a Nazi regime after the Anschluss, he left Austria and became an American citizen. When he was studying for his citizenship exam, he was aghast when his quick grasp of logic allowed him to deduce that the Constitution would permit American democracy to be legally transformed into totalitarianism. That caused him a bit of trouble when the examining judge asked him why he had wished to become an American citizen. Kurt said he wanted to live in a free society, and his own country had been transformed into a dictatorship. "Which of course," the judge said, "can't happen here." Kurt leapt up and cried, "Oh, but you're wrong!" Fortunately, the judge went on and granted Kurt his citizenship..

What did Kurt mean? No one knows exactly, but since the US Constitution (with some exceptions as stated in Article V) puts no limits on the type or number of amendments, it is completely possible to alter it so we could have a supreme monarch, no freedom of speech, and continual surveillance of our private lives. Plus anything else you want, really. So Kurt's conclusion was a simple matter of logic. You just wonder why the Judge, a lawyer presumably, thought otherwise.

Although a logician of first order, Kurt's ability to deduce correct conclusions from a set of basic premises seems to have left him. In his late seventies he somehow deduced someone was poisoning his food, and in early 1978 he died of malnutrition caused by psychosis.

References

On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Kurt Godel, Dover (1992). An English translation in a paperback. But be warned! This is tough going!

"On Formally Undecidable Propositions of Principia Mathematica and Related Systems" is also online. Since Kurt's symbolism is now somewhat out of date, you can try the annotated version of his paper at http://www.research.ibm.com/people/ h/hirzel/papers/canon00-goedel.pdf. This helps explain things when Kurt splashes up a set of symbols and says what you have is a recursive formula ".. as the reader may readily see". But the paper is still tough going. One good thing, is that Kurt does explain in a footnote why his proof is a real proof and not just a sophisticated version of Richard's paradox. It's subtle reasoning, but not difficult to follow.

Godel's Proof, Ernest Nagel, James Newman (Forward by Douglas Hofstadter), New York University Press (2002). A simplified treatment, but still goes through the steps of what Kurt did. Probably the best introduction for the serious student. It might be a bit much for the completely mathematically challenged.

Who Got Einstein's Office? Eccentricity and Genius at the Institute for Advanced Study, Edward Regis, Perseus Books (1987). The first chapter is about Kurt and arguably is the best chapter of the book.

Incompleteness: The Proof and Paradox of Kurt Godel, Rebecca Goldstein, Norton & Company (2005). A general description of Kurt's life and his famous theorem. However, a personal opinion is the explanation of the proof in Godel's Proof (above) is clearer and more exact. For instance, in this book Godel's numbering system for transforming expressions, proofs, and theorems into a unique number (the famous "Godel Numbers") is only loosely explained as something like codes you used to write notes in school. Presumably this is to ease things for the non-mathematical and it's pointed out that the rigorous method used by Kurt is more difficult.

Actually, Kurt's system is extremely simple on its own, and with a little explanation in logic formulation (i. e., "If x, then y" is the same as "x->y") anyone with middle school math can understand Godel's numbering method. Any background information - such as taking advantage of the Fundamental Theorem of Arithmetic - can be explained as you go along.

The big problem with not fully explaining Kurt's numbering system it is you might miss the point that Kurt's proof is valid for arithmetical systems of the type developed by Russell and Whitehead and which are derived by mathematical logic. Kurt did not prove there are unprovable truths in credos of philsophy, religion, or politics.

Godel's Theorem - An Incomplete Guide to Its Use and Abuse, Torkel Franzén, A K Peters, (2005). Very nice and readable book making sense of and also showing the nonsense in what people say about Godel's theorem. A good book to remind people that Godel's theorems are about - we must again emphasize - formal mathematical systems not the U. S. Constitution, not the Bible.

"Does Godel Matter? The Romantic's Favorite Mathematician Didn't Prove What You Think He Did", Jordan Ellenberg, http://www.slate.com/id/2114561/ Jordan is professor of math at Wisconsin. This review does a good job of demystifying what Kurt did. Professor Ellenberg makes a few important points. The axiomatic method defines things by listing their properties. On the other hand it is possible to conceive objects differently and yet they share common properties. So numbers may have different provable properties depending on how they are defined, and one of those properties may be whether or not there are statements about numbers that cannot be proven. So Kurt's theorem may be true for some definitions of numbers, but not for others, and it is true for the definition of the Principia Mathematica. The same points can be made for Alan's work. Define "solving a problem" for a computer properly, and you can prove there are problems that can't be solved. Define "solving a problem some" some other way, and a computer may very well be able to solve all problems. But one important point to remember about Kurt's theorem is not how much it changed mathematics, but how little it changed it.

"Shaken Foundations or Groundbreaking Realignment? A Centennial Assessment of Kurt Godel's Impact on Logic, Mathematics, and Computer Science", Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science,2006, John W. Dawson, p. 339. A brief paper also stating that outside of logic the effect of Godel's theory on the field of mathematics is essentially nil.

"Does Godel's Theorem Matter to Mathematicians", Gina Kolata, Science Vol. 218, pp. 779-780 (1982). Kind of an answer to the question whether Godel's theorem is simply a logicians trick and isn't a "real" mathematical proof. This paper shows some examples that are real but for one reason or another can't be proven - again it must be stressed - within their system.