You may only read this site if you've purchased Our Kampf from Amazon or Powell's or me
• • •
"Mike and Jon, Jon and Mike—I've known them both for years, and, clearly, one of them is very funny. As for the other: truly one of the great hangers-on of our time."—Steve Bodow, head writer, The Daily Show

"Who can really judge what's funny? If humor is a subjective medium, then can there be something that is really and truly hilarious? Me. This book."—Daniel Handler, author, Adverbs, and personal representative of Lemony Snicket

"The good news: I thought Our Kampf was consistently hilarious. The bad news: I’m the guy who wrote Monkeybone."—Sam Hamm, screenwriter, Batman, Batman Returns, and Homecoming

July 23, 2009

Goedelian Blogging

By: Bernard Chazelle

Commenter SunMesa made an interesting parallel between the completeness of ethical codes and Goedel. Roughly, what Goedel showed is that if you give yourself a finite (or finitely generated) system of axioms and inference rules so as to be able to prove things in arithmetic (like, "every even number >2 is a sum of 2 primes") , then one of two things must happen: either your system is inconsistent (ie, you can prove that something is both true and false) or there are true statements (in first order logic, ie, of the kind you're familiar with) that cannot be proven. Goedel then proved a second theorem; essentially if your system can prove its own consistency then it is inconsistent.

As math goes, proving Goedel's theorems is not hard. But, like quantum mechanics, to figure out, at a philosophical level, what it's all about is tricky. In fact the debate is still raging. That's perfectly fine. What I am very skeptical about is any attempt to use "Goedel" outside mathematics. I've read statements to the effect that sociology cannot be proven to be consistent. That's utter, embarrassing nonsense. The Incompleteness Theorems concern only formal systems and are meaningless in any other context.

That said, I believe in the power of analogy, which is why the commenter's point is well worth thinking about. Goedel's result is an exotic byproduct of self-reference, which is among the most important concepts from the last 100 years. Magritte used it in his paintings. The Abbott and Costello skit, "Who's on First?" is entirely premised on that. If Goedel inspires people to think creatively, all the better. For non-scientists I highly recommend the book by Hofstadter ("Goedel, Escher, Bach"). Unfortunately, when it comes to Goedel, there's a tendency in the humanities to view the mention of a famous math guy with an umlaut in his name as a mark of authority. This tendency does not have the ATR seal of approval.

Speaking of which, Jon's blog posts have proven to be not only truthful, but morally beneficial to the world. As a reward, the Goddess of Blogging, who is the niece of the Flying Spaghetti Monster, has granted Jon eternal life on earth. All he has to do now is continue writing truthful posts, for eternity, and thus shower the universe with infinite moral good.

Any blog post consists of a finite number of characters, so Jon has been effectively granted the awesome power to write every conceivable truthful post. Your favorite truth may take a while to show up at ATR but, patience, patience, Jon will produce it one day!

What Goedel proved is that, sadly (get the kleenex ready), Jon must be evil or only partially good. Well, Goedel never said that. I did. The person who came closest to that statement was Alan Turing, who said to the head of Bell Labs: "You can be smart or infallible, but you cannot be both -- and in your case you cannot be either." The first part of the quip was a correct consequence of his seminal work on computing; the second part only expressed his abject disdain for AT&T management.

Consider this blog post:

Jon will never write this post.

If one day Jon writes the post above, then he will be writing something false, since writing the post will contradict its meaning. Needless to say, this will cause enormous harm all around the world: it will prove beyond any reasonable doubt that Jon is evil. On the other hand, if Jon never writes that post, then the very fact of never writing it will make its meaning come true. So there you'll have a truthful post that Jon will never write. This will deprive everyone of much moral good. How can Jon do that to us? He was granted all of eternity and he missed a simple truth which is only 6 words long!!!!! He may be a good guy, but come on, that's one nasty oversight. I'd call his goodness partial, and that's because I am a nice guy. So I've proven that an eternal Jon cannot be perfectly good.

Now let's move over to the world of similes. What I did earlier was sketch a hand-waving explanation of something rigorously correct, ie, Goedel's first Incompleteness Thm. Now I will use the language of "this is like." My meta-ethical principle about torture is to decree that there is no ethical code for TBS. Here is the analogy. I, as co-blogger, will post:

Jon will never write this post.

I will instruct Jon never to write this post. In this way, the post will now be truthful, since (1) I wrote the post, not Jon, and (2) Jon never did and never will write a post with these words. On the other hand, that important truth has now been posted and no one is being denied the enormous moral good that comes with that.

Problem fixed? Well, not quite. By absolving Jon, I've put myself in trouble. I'll leave this as a homework assignment. If some kind soul comes to bail me out then that person himself will be in trouble. What you're doing is building higher and higher levels of rescuing operations. This goes to infinity. Philosophers have long been intrigued by this idea. Some have even said this is what defines consciousness. To which I say, Whenever you hear, "this defines consciousness," check your wallet.

In matters of self-reference, Goedel is cool. But Tony Blair is even cooler. The guy actually said: "I don't make predictions. Never have. Never will." Blissfully unaware of it. Which proves that, after all, maybe Goedel's swirls of infinitude prove not what it is to be conscious but what it is to be nonconscious.

One final point. Some, like Penrose, have argued that maybe a computer (or logic) cannot be sure that Jon will not write something so stupid as the post above, but surely we, humans, obviously know he won't. Therefore, the human mind is superior to a computer. I believe the conclusion but not the proof. Why? I'll simply ask Penrose. And exactly how do you know that Jon will not write this post? Penrose will say, Oh Bernard, come on, you know that Jon is not human. He's an automaton programmed to apply the rules of Zermelo-Fraenkel set theory augmented with the Axiom of Choice (ZFC). Well, Penrose, don't insult my intelligence! Of course I KNEW THAT! But so what? " Well, Bernard, obviously that system cannot produce falsehoods therefore Jon will not write the post." Hmm... so you're saying that "obviously" ZFC is consistent.... Obviously... obviously.... obviously.... obviously... "Why do you keep saying "obviously"? Because I heard that if you keep saying long enough that something nonobvious is obvious then it eventually becomes obvious.

— Bernard Chazelle

Posted at July 23, 2009 03:19 PM

Did you know that you can make a good living as a blogger just by making fun of the crazy shit Republicans say?

You guys are working too hard.

Posted by: SteveB at July 23, 2009 04:48 PM

I'll second the recommendation of Gödel, Escher, Bach.

Posted by: Cloud at July 23, 2009 04:52 PM

Rob will never write this comment.

Posted by: Rob Payne at July 23, 2009 05:08 PM

Commenter SunMesa made an interesting parallel between the completeness of ethical codes and Goedel.

Having been thus called out, I feel compelled to comment, if only briefly. I will shortly be away from internet access for some days, but I look forward to reading the discussion when I return. These are some deep waters.

What I am very skeptical about is any attempt to use "Goedel" outside mathematics. I've read statements to the effect that sociology cannot be proven to be consistent. That's utter, embarrassing nonsense. The Incompleteness Theorems concern only formal systems and are meaningless in any other context.

I am similarly skeptical, although I am not well prepared to delineate what lies "outside" mathematics. My reference to Godel and incompleteness was sparked by the "i.e." in your Counterpunch essay equivalencing an ethical code with a universal decision procedure. The latter, I would contend, must incorporate a formal system, and moreover, one sufficiently general that it can generate mathematical proofs.

Goedel's result is an exotic byproduct of self-reference, which is among the most important concepts from the last 100 years.

I did read Godel, Escher, Bach some 30 years ago, along with some some additional arcane material concerning the incompleteness theorem that, shall we say, I skimmed over.

I have often heard Godel's result characterized as a 'trick' depending on self-reference. Has this actually been established? To put it more explicitly, consider Proposition A: "All unprovable truths in (sufficiently general) formal systems are self-referential".

It strikes me that A is possibly true, possibly self-referential, and possibly unprovable, or some combination thereof.

At this point I would need a stiff drink to proceed further, and need to finish packing. Good luck, all.

Posted by: SunMesa at July 23, 2009 06:37 PM

SteveB: I wish I could say I enjoy blogging about politics, but I don't. The ugliness of the people in politics disgusts me. But math, music, philosophy, humor, yes I really love that stuff...

Rob: You wouldn't do this to us, would you? So I have to assume that Jon impersonated you.

SM: Self-reference is a tricky thing, right, because I can hide it very well. But if by that you mean, are all unprovable sentences obviously self-referential, in the sense that they look like P(t), where t refers to P(t), then the answer is clearly no. There's nothing self-referential about the unsolvability of Diophantine equations, or the Continuum Hypothesis, etc.

I believe that diagonalization is always needed in the proof, however. Certainly there's a lot of that in the proofs of the 2 examples I mentioned. Of course, maybe one can argue that self-reference and diagonalization are related. I guess they are. But the point is that they need not appear explicitly in the statement. They can be hidden in the proofs.

I've always viewed Goedel's proof as a nice twist on Cantor's work. I don't understand why Cantor doesn't get more credit. They were two madmen, but Cantor is the one who built the madhouse.

Happy packing (and a good trip, wherever you're going).

Posted by: Bernard Chazelle at July 23, 2009 07:26 PM

Naw, Jonathan has much better taste than that. Besides, I’m a habitual liar and that’s the truth.

Seriously, your essay on torture is outstanding. I couldn’t agree more with your conclusion.

Posted by: Rob Payne at July 23, 2009 11:34 PM

"That life is worth living is the most necessary of assumptions and, were it not assumed, the most impossible of conclusions."
-George Santayana

Posted by: I do not recommend this site at July 23, 2009 11:37 PM

Hey, Chazelle, I take off my shoes to count over ten. Go back to politics.

Posted by: Rosemary Molloy at July 24, 2009 06:56 AM

This is an amusing post, Bernard, but I object to your description of the proofs as not hard. When I was in eleventh grade, my math teacher loaned me GEB, and after I read it the first thing I did was to get a translated copy of On Undecidable Propositions. I had no prior experience with formal logic and found it very difficult reading. I eventually understood most, but not all of the proof. Four years later, in college, I took a course in recursion theory, and read the paper again. Of course this time, it made much more sense, much more easily, but I still wouldn't characterise it as "not hard." The string of thirty-odd definitions on the way to Theorem 6 is definitely nontrivial, and further, as far as I know no one before Goedel had thought of coding first-order formulae as naturals and performing operations on them. It is hard. That's why there are a number of books trying to help people understand it.

Also, trying to use the Incompleteness Theorems to prove something unrelated to formal systems is annoying, and also amateurish. (I'm not saying this is what SunMesa was doing; s/he was merely analogizing.) This desire to stretch math further than it can go in describing vague philosophical concepts makes me root for a return to natural-language philosophy in spite of my own fondness for formal logic.

Posted by: Save the Oocytes at July 25, 2009 11:54 AM

please, give us a break. the posts on bach and bird and math and whatever aren't good reading and they're off topic. they detract from atr. move 'em to bernardsmusicandmusings.blg and let's keep atr to more political topics.

Posted by: jerry at July 28, 2009 01:57 AM

The mathematical is political.

Posted by: Solar Hero at July 28, 2009 02:16 PM