Tuesday, January 31, 2012

Gödel’s Proof—Or Was it a Spoof?

When it comes to higher math, it’s a good policy to stay cheerful—and to resist the waves and waves of frustration that well up. Take one of the more prominent figures in that field, Kurt Gödel (1906-1978); he is famed for his incompleteness theorems. I managed to find a partial translation of his first paper (link). It was written when Gödel was but 25. He does the job—the job is to humble mathematicians forever—in just 15 pages (the paper is longer, but it begins and ends with the translator’s notes). It’s good to stay cheerful because with effort the essence will emerge—not from fully penetrating the actual originals, mind you, but because with the help of others one can get there. By essence I mean, enough to satisfy me that there is something worthwhile present here.

Gödel labored at a time when mathematicians were endeavoring to prove that various systems of mathematics were both complete and consistent. If they were neither—or one but not the other—the foundations of mathematics were in trouble. Those engaged in such labors were the really big names in twentieth century math: Abraham Fraenkel, Friedrich Frege, David Hilbert, Giuseppe Peano, Bertrand Russel, and Ernst Zermelo. What Gödel proved, and thus upset the apple cart was:

1. If the system is consistent, it cannot be complete.
2. The consistency of axioms cannot be proven within the system.

The reason for good cheer is that Gödel proved the liar’s paradox mathematically.  That paradox originates with Epimenides, an ancient Cretan philosopher-wit who asserted “All Cretans are liars.” If taken as a true statement, it is a lie; if as a lie, it contradicts itself. The modern way is to ponder the truth-value of  “This sentence is false.” Gödel substituted “not provable” for lie or falsity. He showed that such a statement can be formulated mathematically so that it is equally contradictory: if proved it is false, if disproved it is true.

Now completeness asserts that every proposition framed by a formal system can be proved. But consistency demands that the outcome of any process must result either in truth or falsehood, never both. Gödel therefore showed that mathematical systems are either one or the other: if they are consistent, they are incomplete, if they are complete, they are inconsistent. The consistent system must exclude the formula Gödel framed using the rules of the system and thus be incomplete. The complete system will include the Gödel number but, producing at least one paradoxical result, will be inconsistent.

But what Gödel actually proved, it seems to me, is that Man is not God—although we kind of knew that already. He himself was not only a true believer, he bought the traditional package with all of its frills and was dead certain that he would survive his own death. Good for you, Kurt Gödel. I bet you are still chuckling over your life’s achievements somewhere out there in the transcending ether.

3 comments:

  1. There are technically mathematical systems that can be both complete and consistent, like Presburger Arithmetic, but they are very, very weak -- in order to get that result you have to give up things like multiplication. As I like to put it, first grade math is complete and consistent; anything more requires being brave enough to take at least a little risk. Math's an adventure as much as anything else.

    The only reason I know about Presburger Arithmetic is that there was a big discussion a while back on some math blogs I occasionally visit about claims that there might be a proof that full arithmetic was really inconsistent. The consensus seems to have been that the proof failed, but it was interesting seeing mathematicians seriously consider it.

    ReplyDelete
    Replies
    1. Strikes me, Brandon, that we're witnessing a kind of fashion here. Russell started it in 1901 when he made waves by showing early set theory to be contradictory--and after that if you had the right stuff, you too could shine by kicking some statue off its perch. The deeper current arguably is cultural...

      Delete
    2. I think you're probably right; imagine the status of the mathematician who managed to prove that all other mathematicians had beeen doing almost everything wrong.

      In this particular case, I think there's also another cultural factor: fear of the infinite. Nelson, who came up with this attempt at a proof, is a finitist, if I recall correctly -- he wants a mathematics with fewer untamed infinites. Something a little less sublime, a little more cozy.

      Delete