Back in the 1930′s, Kurt Godel proved two amazing facts about arithmetic: First, there are true statements in arithmetic that can’t be proven. Second, the consistency of arithmetic can’t be proven (at least not without recourse to logical methods that are on shakier ground than arithmetic itself).
Yesterday, I showed you Gregory Chaitin’s remarkably simple proof, of Godel’s first theorem. Today, I’ll show you Shira Kritchman and Ron Raz’s remarkably simple (and very recent) proof of Godel’s second theorem. If you work through this argument, you will, I think, have no trouble seeing how it was inspired by the paradox of the surprise examination.
Start with this list of statements:
- It takes more than 10000 characters to specify the number 1.
- It takes more than 10000 characters to specify the number 2.
- It takes more than 10000 characters to specify the number 3.
and so forth.
Obviously, statements 1, 2 and 3 are all false, since it only takes a single character (namely “1″) to specify the number 1, and a different single character (namely “2″) to specify the number 2. But if you continue this list long enough, you’ll eventually get to some true statements. Yesterday we saw a proof that none of those true statements is provable.
But suppose that, undeterred by the proof, we are determined to identify a specific true statement on the list. Here’s our strategy:
- First we write down the first gazillion statements on the list, where a gazillion is some number so big that we’re sure to have included some truths.
- Next we go down the list, eliminating false statements. Notice that if we’re willing to work long enough, every false statement eventually gets eliminated — we just keep trying shorter-than-10000-character prescriptions and crossing off the numbers they describe. This leaves us a list of candidates.
- Suppose there’s just one true statement on the list. Then eventually we cross all the others off, and learn that the one remaining candidate is true (because the list was so long there had to be at least one true statement). In fact, we’ve just proved (by process of elimination) that this statement is true. But we learned yesterday that no such proof is possible. Conclusion: There can’t be just one true statement on this list.
- Suppose there are just two true statements on the list. Then eventually we’ll cross all the others off, leaving two candidates, at least one of which is true. But we’ve already proved that there can’t be just one true statement, so these must both be true. In fact, we’ve just proved they’re true. Which is impossible. Conclusion: There can’t be just two true statements on the list.
- Do you see where this is going? There also can’t be just three true statements on the list, or four, or five, or any other number. Yet we know there are true statements on the list! Something’s wrong here!!!!!
Okay, what went wrong? Answer:
- Our argument relies on the fact that every statement on our list must be unprovable. Why should we believe that? Well, we proved it yesterday; that’s why!
- Actually, our argument relies on a bit more — it relies not just on the fact that every statement on our list is unprovable, but that we can prove their unprovability. But again, we did that yesterday.
- The only way out of this is to conclude that there’s some gap in yesterday’s proof.
- But there’s only one thing we used yesterday without proving it: We began from the assumption that our arithmetical reasoning is consistent.
- So that must be where the gap is — and it must be impossible to fill that gap! In other words, it must be impossible to prove that arithmetic is consistent.
There’s just one other way out: If arithmetic actually is inconsistent, then all bets are off and we can prove its consistency — but in that case, of course, our conclusion will be wrong. In any event, there are very few people who think this is a contingency worth worrying about.