Raw Thought

by Aaron Swartz

Incompleteness: The Proof and Paradox of Kurt Gödel

Book cover

Gödel was a hacker. He attended the meetings of the Vienna Circle, one of the most important philosophical groups in history, and sat quietly, convinced they were all wrong. Others might try to argue them out of it. Not Gödel. Perhaps (rightly) he thought that rational argument would get him nowhere with people so detached from reality. So he decided to prove them wrong.

The result was Gödel’s incompleteness theorem, one of the most celebrated results in mathematics and logic, elegantly proving that any mathematical system complicated enough to do basic arithmetic contains statements which, while true, cannot be proven within the system.

But even this was to no avail, the Vienna Circle continued to insist the proof was bogus or irrelevant. (The Vienna Circle insisted the world was simply language-games, with rules and structures. Gödel, by showing something that was clearly true to us but not provable from within the game, thought he had proved that such things, like numbers, have an independent reality.) Gödel, an incredibly odd and delusional figure, remained quiet for many years, practically confiding only in Albert Einstein, and little at all after Einstein’s death.

This is a very bad book. It rambles and prattles and occasionally repeats itself practically verbatim. (It is the result of a project to improve science writing simply by paying famous authors to write about scientific topics. Perhaps the payment should be contingent on some measure of quality in the result.) But it is a compelling story and Gödel’s proof is so brilliantly beautiful that it should be learned by all educated people. I had never seen it presented in any real detail before and once I got to its key principle I exclaimed and tossed the book down and paced, admiring its brilliance. But there are many sources who will explain the fairly simple idea. I’d love to tell you about it myself.

You should follow me on twitter here.

February 12, 2007


One of the best explanations of Gödels incompleteness theorem can be found in Douglas R. Hofstadter’s “Gödel, Escher, Bach: an Eternal Golden Braid”. The book is highly recommended and really a piece of art itself.

posted by amix on February 12, 2007 #

I don’t think that characterization of the Vienna Circle is very accurate. Read the Wikipedia for a better description of their philosophical positions.

posted by ThomasW on February 12, 2007 #

amix, congratulations on being able to get through GEB. I’d heard great things about the book and bought a copy when I saw it in a local bookstore.

Unfortunately, he struck me as the nerd equivalent of Wiliam F. Buckley, Jr. in terms of filling a lot of space (WFBJr loves to hear himself talk) while managing to say very little - at least that’s what he did in the preface, which turned me off so strongly that I never got into the actual book.

posted by Brian Donovan on February 12, 2007 #

I second amix’s recommendation of GEB.

If you want a much shorter and more focused intro to Gödel’s first incompleteness theorem though, see the wonderful exposition of Ernest Nagel and James R. Newman. This last work is the one that piqued the interest of Hofstadter (and Gregory Chaitin and many others) in Gödel’s theorem when it came out in ’50s.

There is also an excellent biography by John W. Dawson, Jr..

posted by joseph knecht on February 12, 2007 #

I recall a survey of prominent scientists which asked them which single book they would want to have with them if they were stranded on a desert island - the book mentioned most often by far was “Godel, Escher, Bach”. I have read it a couple of times myself and it would be the book I would take with me.

posted by Ian Gregory on February 12, 2007 #

As it happens, I just got tickets to see the author lecture through my school. Anyone in Portland care to join me?

posted by David McCabe on February 13, 2007 #

Even Roger Penrose gives an overview of the proof, as well as of most of mathematics and physics :) in the Emperor’s new Mind.

posted by Steve Balogh on February 13, 2007 #

Not having read New Mind, I’d be wary of Penrose’s exposition. He is a brilliant mathematician, to be sure, but he is also a mystical thinker, and I would be surprised if he didn’t mix in, perhaps subtly, unwarranted interpretation or misapplication of the theorems.

Penrose’s approach seems to be: “Hmmm, what would I like to be true? … Alright, now how would the universe need to be for that to be possible?” And then he goes on to think up a brilliantly clever reason that the universe might be compatible with his desires. For example, “quantum morality” (scare quotes, not quoting Penrose), or the massless charged particle he postulates to get cyclical time.

Disclaimer: I could be misunderstanding and misrepresenting him — his lectures are difficult to follow.

posted by David M. on February 14, 2007 #

I’ll second amix recommandation. GEB is a very interresting and well written book. And unfortunately for you, the french translation bring event more to it. Douglas Hofstadter wrote the french preface to the french translation himself.

Apart of this, this book is really brilliant !

posted by François Granger on February 14, 2007 #

You might be interested in E. C. R. Hehner’s version of the proof; see his paper Beautifying Godel for details.

The distinction between program and data, the use of the character string data type, the use of an interpreter, and counting from zero allow the proof to be reduced to three lines.

posted by Alan on February 15, 2007 #

I second Brian’s recommendation to skip GEB. It’s very cleverly written, but the insights it offers are few. For example: the author dedicates a sonnet to Russel’s paradox when a sentence would suffice. It’s also guilty of jumping to the “exciting” popular science subjects - AI, DNA, robots, etc. - while providing little background or depth.

posted by on February 16, 2007 #

But it’s so very clever!

posted by David M. on February 17, 2007 #

Actually, I’d advise you to try reading the original paper, which you can find here: http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf (and there are other translations too, some of them using either the original or a newer logic notation); try googling for “on formally undecidable” and Gödel.

It’s very interesting to read the proof itself, instead of the usual human-translation.

posted by Hernan Moraldo on February 24, 2007 #

GEB is very lucid if extremely long-winded and tangential. I had a great time reading it as a teenager. I don’t know if I’d have the patience for it now. But it presents Gödel’s proof in a way that’s both complete (no serious technical gaps) and quite accessible to non-math people. I later took the standard intro-to-mathematical-logic class (Math 125A at Berkeley) whose main result is Gödel’s proof, and found I already understood the subject pretty well just from having read GEB. However, if you want a more serious (but still accessible) treatment from a standard math book, Herbert Enderton’s “Introduction to Mathematical Logic” is quite good. It treats proof theory, model theory, and I think discusses axiomatic set theory to some extent, though he has a separate book for that. Really, everyone should know a bit about this stuff.

Wikipedia’s coverage of these subjects is also quite good. I guess I’d start with [[Mathematical logic]] and follow the links from there.

posted by Paul on March 1, 2007 #

You can also send comments by email.

Email (only used for direct replies)
Comments may be edited for length and content.

Powered by theinfo.org.