Today, I’m going to give you a short, simple proof of Godel’s First Incompleteness Theorem — the one that says there are true statements in arithmetic that can’t be proven. The proof is due to Gregory Chaitin, and it is far far simpler than Godel’s original proof. A bright high-schooler can grasp it instantly. And it’s wonderfully concrete. At the end, we’ll have an infinite list of statements, all easy to understand, and none of them provable — but almost all of them true (though we won’t know which ones).
Chaitin’s proof, like Godel’s, is inspired by a classical paradox — in this case, Berry’s Paradox as opposed to the Liar Paradox (both of which I described yesterday).
We start by observing that some numbers are more complicated than others. The 10,000 digit number that starts off 10101010101010101….. and continues the same way is somehow less complicated than a random 10,000 digit number.
Kolmogorov formalized this notion by defining the “complexity” of a number as the length of the shortest prescription (in some fixed language) for writing it down. The number above has a 48-character prescription: “Write down a 1, then a 0, then repeat 5000 times”. That makes it pretty simple.
Now suppose we want to find a more complicated number — one that requires at least, say, 60 characters to prescribe. We know there must be many such numbers, but we’d like to find a specific example — together with a proof that our example can’t be prescribed in less than 60 characters. So we write a computer program, called Finder60, which searches for examples-with-proofs. Ideally, the program outputs something like: “I have found a proof that the number 2834932709472398472328923478902342903848927189374901742309842398742 cannot be prescribed with fewer than 60 characters.”. Finder60 searches systematically, so if there’s such a number/proof combination to be found, Finder60 will find it. Otherwise, it keeps on running forever.
We can also, of course, write programs called Finder90, Finder120, Finder10000 and so on, to find ever-more-complicated numbers together with proofs that they are complicated.
Once you’ve written the code for Finder60, you only have to tweak it slightly to get the code for Finder10000 — and the code gets only slightly longer in the process. Basically, you just change all the 60′s to 10000′s, replacing two-digit strings with five-digit strings. Not much difference.
So if the code for Finder60 is, say, 5000 characters long, then the code for Finder10000 is just a bit more than that — say 5200 characters.
Now suppose M is any number that provably requires more than 10000 characters in its prescription. Then Finder10000 will find it and print it out. Which means we have the following less-than-10000-character prescription for M:
Uh oh! If prescrbing M provably requires more than 10000 characters, then M can be prescribed in fewer than 10000 characters. Contradiction!
Conclusion: There must be no such M. That is, no number can be proved to require more than 10000 characters in its prescription.
But surely some numbers do require more than 10000 characters; after all there are only finitely many ways to prescribe a number with fewer than 10000 characters, which leaves infinitely many numbers left over.
So what’s a true statement that can’t be proven? Answer: Any true statement of the form “The number M cannot be prescribed in fewer than 10000 characters”. No matter what M you plug in , this statement must be unprovable. If you plug in M=1 or 2, you’ll get a false statement. But for most values of M (though we don’t know which values!) you’ll get a statement that’s true, but unprovable.
Isn’t that about the coolest trick ever? Well, it turns out that you can add another twist to make it even cooler. That’s where the surprise examination paradox comes in. I’ll explain it all one day later this week, though you won’t know which day till you log in that morning.