Godel’s theorem (or at least one of Godel’s theorems) says that no matter what axioms you adopt, there will always be true statements in arithmetic that can’t be proven. In Chapter 10 of The Big Questions I give an explicit example of such a statement, involving Hercules’s ability to win a certain game against a very persistent hydra.
There are many popularizations of Godel’s original argument, of which at least one (by Nagel and Newman) is superb. They do a marvelous job of boiling the argument itself and the surrounding issues down to a little over a hundred sparse pages. But I can boil it down further, into a single blog post. I can do this via the magic of one of my favorite expository techniques, a technique I call “lying”. I will lie to you throughout this post, by sweeping important technical details under the rug and (slightly) corrupting some important ideas to make them easier to grasp—but without, I think, sacrificing the flavor and the gist of the argument. At the end, once we’re clear on the big picture, I’ll ‘fess up to some of those lies.
Here, then, is (more or less) how Godel proved that arithmetic contains true but unprovable statements:
Step One: Start by dividing all numbers into two categories. We’ll call a number “good” if it can be written as the difference of two primes and “bad” if it can’t. (Here a “number” means a positive integer.)
Step Two: Next make a list of all possible statements about arithmetic. Something like this:
1. 3 is a prime number.
2. 2 plus 3 equals 7.
3. Every number is the sum of at most four squares.
4. x is a prime number.
5. 2 plus 3 equals x.
Some of these statements, (like numbers 1 and 3) are true. Others (like number 2) are false. Still others (like numbers 4 and 5) contain variables and hence are neither true nor false unless the value of the variable is specified.
Step Three: When we make our list, let’s be sure to follow this rule:
Rule A: Every provable statement should go next to a good number and every non-provable statement should go next to a bad number.
The list above violates this rule. After all, 2 is the difference of two primes (it’s 7 minus 5), so 2 is a good number, so statement number 2 should be provable. Since we’re pretty confident that “2 plus 3 equals 7” isn’t provable, we should move it someplace else on the list, say to line 7. Revise the list as needed so Rule A is always obeyed.
Step Four: After we’ve rearranged our list in accordance with Rule A, let’s peruse it a bit. Suppose—just suppose—that we happen to find a line like this:
24537. 24537 is a bad number.
That is, statement number 24537 just happens to mention the number 24537, and declares that it is a bad number.
Given this, we can figure out whether 24537 is good or bad. Suppose first that it’s good. Then (because of Rule A), statement #24537 must be provable, and hence true. But statement #24537 says that 24537 is a bad number. So if 24537 is a good number, then it’s a bad number. That makes no sense, and we conclude that it can’t be good.
Okay, then, 24537 is bad. So the statement “24537 is a bad number” is true. But that very statement is written next to a bad number, which according to Rule A, means it’s unprovable. Conclusion: “24537 is a bad number” is both true and unprovable. Our quest for a true but unprovable statement is complete.
Step Five: Of course it would be just as good to find a line like
198764. 198764 is a bad number.
or
2381212. 2381212 is a bad number.
or
37999999. 3799999 is a bad number.
Any one of these lines would be enough to demonstrate that there is a true statement in arithmetic that is not provable. But of course, maybe there simply are no such lines.
Step Six: Let’s revise our list again. In addition to following Rule A, we’ll follow one more Rule:
Rule B: If a statement contains a variable, and if that variable is replaced by the statement’s own number, the number on the resulting statement should be the square of the number on the original statement.
To understand what that mouthful means, suppose that statement 6 just happens to be:
6. x is prime.
Then Rule B requires that statement 36 must be
36. 6 is prime.
Likewise if statement 7 happens to be:
7. 2 plus 3 equals x
then Rule B requires that statement 49 is:
49. 2 plus 3 equals 7.
Step 7:Once we’ve revised our list according to Rule B, let’s scan up and down the list for the following statement:
x2 is a bad number
This statement has to be somewhere on our list, because every statement about arithmetic is somewhere on our list. Let’s just suppose it happens to be statement number 13:
13. x2 is a bad number.
Then Rule B tells us what’s on line 169 (169 is the square of 13):
169. 132 is a bad number.
Or in other words:
169. 169 is a bad number,
So we have found exactly the kind of entry that we agreed in Steps Four and Five provides us with a true but non-provable statement, namely:
169 is a bad number
or, eliminating our value-laden terminology:
169 is not the difference of two primes.
The existence of this true but unprovable statement is a necessary consequence of our ability to make a list that obeys Rules A and B.
Step Seven: Are we done? Not quite. How do you know we can make a list that obeys both Rule A and Rule B? We needed to revise our list so it follows Rule A, and then revised it again so it follows Rule B. But when you revise your list to implement Rule B, you might screw up Rule A. When you re-revise to make sure you’re following Rule A, you might screw up Rule B.
Here’s what Godel did: He gave an explicit recipe for building a list that obeys both Rule A and Rule B. Once you’ve got that list you’re done.
Confession: Actually, that’s a lie. In order to make things work, Godel needed a considerably more complicated definition of “good” and “bad” numbers; our definition in terms of differences of primes doesn’t quite work. And in Rule B, instead of squaring, he needed a more complicated rule to give the number of the new statement that results when you plug a statement’s number into itself. But this more complicated rule still has a purely arithmetical description, which is all we need to make the argument work.
(In fact, Godel went much further. His recipe constructs a list where every grammatical relationship between statements is reflected by an arithmetical relationship between their corresponding numbers. Rule B—or something like Rule B—is one very special case of that phenomenon.)
The Bottom Line. Our true but unprovable statement turned out to be 169 is not the difference of two primes. This is a bogus example, because our Rules A and B are simplifications of the rules Godel actually implemented. But the real example has exactly the same flavor; it says that a particular number fails to have a particular (purely arithmetical) property. The number itself, and the description of the property, are too gigantic to squeeze into this post, but are no less significant for being large.
One thing that I suppose confuses most people is that you have, in fact, proven that the “true but unprovable” statement is true. My understanding of Godel’s theorem is that you should have said: “true but unprovable from the axioms of arithmetic combined with first-order logic” or something like that.
Even then, you still need to assume that arithmetic is consistent, because if it is inconsistent, then you can prove any statement, so that there could be neither “false and unprovable” nor “true and unprovable” statements.
Speaking of which: in step three, if arithmetic were inconsistent, then every statement, being provable, should be associated with a “good number”.
Also, my understanding of the halting problem is that you cannot enumerate all unprovable statements; that is, there are unprovable statements which you cannot prove to be unprovable. I am not sure how that affects your proof.
Is there any introductory, self-contained textbook on logic that includes Godel’s and Turing’s results?
It has been decades since I learned this as a math major. But if I recall right, all you need are that whatever set of axioms of arithmetic you choose to accept has to have a finite number of elements. You can recombine these only a countably infinite number of ways whereas the set of propositions to be proved is uncountably infinite.
MW: No, you do not need a finite number of axioms. All you need is a finite procedure for determining what is and is not an axiom. The usual axioms for arithmetic (the so-called Peano axioms) are infinite in number, and Godel’s theorem still applies. I’ve discussed this at some length on pages 93 through 97 of The Big Questions.
Steve: maybe MW has a point: a finite procedure to decide what is or is not an axiom contains a finite amount of information. That seems* to imply that the number of statements that can be proven (or disproved) from the axioms is countably infinite. The number of arithmetical statements is uncountably infinite, ergo not all of them can be proven or disproved. (That’s a kind of diagonal slash, of course.)
The asterisk marks what I see as the weakness of my argument.
Snorri: The number of arithmetical statements in a given language is countable.
I like the post a lot, even if there are lies in it. How did you boil it down like that? Did you try hard to show your rules A and B would work, or did you realize early that they wouldn’t? Do you know a smallish number for which determining whether it is a difference of two primes is infeasible on today’s computers? Can you build on the argument (correcting it) to do better than Nagel and Neuman (which I haven’t looked at)?
The number of arithmetical statements in a given language is countable.
Of course…since the statements have finite length. I got carried away. Anyway, that just goes to show that the weakness in your argument is always where you least expect it, as Merlin implied in “Excalibur” (1981).
Dan Grayson: I did not try hard to show that my Rules A and B would not work, and I don’t actually know that they wouldn’t, but it seems wildly implausible. The rules one gets by following Godel’s prescription are immensely more complicated to state, and it’s clear why they have to be, because the statements of the rules reflect all the different rules of inference that are allowed in your logical language. So I’d be very surprised if much simpler rules could be made to work.
Another issue: As far as I know, there might be only finitely many numbers that are differences of two primes. (This seems extremely unlikely, but I don’t think the negation of this statement is known.) If that were so, it would certainly mean Rule A can’t work.
I chose “differences of two primes” because it was the first criterion I happened to think of that was not finitely checkable. (“Sum of two primes” can’t work, because any number that is the sum of two primes is clearly provably so, via a finite search.) I went to Google to find out whether it was known that every even number is a difference of two primes, which, if provably so, would also eliminate any chance of making Rule A work. I discovered that this isn’t known. (It does seem to be widely conjectured, though, and if it’s ever proved, then there goes my rule A.) Presumably it’s known for even numbers less than some N, but I have no idea what N is.
As far as doing a better job than Nagel and Newman, it’s often possible to do a better job by standing on the shoulders of giants. But they do such a good job that I’m not sure it’s worth the effort to try to improve on it.
You might be interested in reading this paper that George Boolos published 15 years ago, “Godel’s Second Incompleteness Proof Explained in Words of One Syllable”:
http://www2.kenyon.edu/Depts/Math/Milnikel/boolos-godel.pdf
Also, I’m sure you know about this but there’s an interesting paradox that follows if we assume some first order axiom system A for arithmetic is consistent, and we take another important theorem by Godel, The Completeness Theorem:
http://mathworld.wolfram.com/GoedelsCompletenessTheorem.html
Since A is consistent, then as a consequence of the second incompleteness theorem, we know that A’ = A + Provable_in_A(“1=2”) is consistent too… and then by the completeness theorem we know that there’s a model M of arithmetic that makes A’ true. Of course M would have to be nonstandard in this case and contain some “infinitary” numbers…
““24537 is a bad number” is both true and unprovable.”
I am feeling tired and must have missed something, but wouldn’t putting this statement after the number 2. make it both true (which it is) and provable (because it follows number 2, which is a “good number?”
Obviously I am missing why it is important that the number in the statement is put after its own number. If the statement states any truly bad number to be bad, why not pair that with a different “good” number and be done with it?
Phil: You can’t make a statement provable but writing it in a particular spot on a list. Statements are provable or not independent of where you write them. In this case, I chose to obey the rule that provable statements go next to good numbers and unprovable statements go next to bad numbers. So if “24537 is a bad number” is unprovable, then I am not allowed to write it next to 2.
But why is it unprovable that 24537 is indeed a “bad” number if in fact it is a “bad” number? Does it follow from the fact that there are infinitely large quantities of prime numbers, hence one can’t rule out that the difference between two of them will generate the number 24537, thus making it unprovable?
Phil:
But why is it unprovable that 24537 is indeed a “bad” number if in fact it is a “bad” number? Does it follow from the fact that there are infinitely large quantities of prime numbers, hence one can’t rule out that the difference between two of them will generate the number 24537, thus making it unprovable?
No, it does not follow from this fact. If you were trying to prove that 24537 is bad, your first idea might be “let’s try every possible pair of primes”. That won’t work, because there are infinitely many prime pairs. This means that your FIRST IDEA for a proof won’t work, but that doesn’t rule out the possibility of some OTHER proof. There are plenty of cases in mathematics where the first obvious attempt at a proof doesn’t work, but some other proof works just fine.
To see that we’ve produced an unprovable statement, you really do need all of the steps in the argument I’ve given here.
Thanks. That makes sense.
Matthew: thank you for the links. My understanding of Godel is closer to Boolos’ than to that of Landsburg’s; that is, I believe the “true but unprovable” statement to be true and unprovable*; but I also believe that it cannot be proven to be true, and that it cannot be proven to be unprovable*. Or to put it another way, I take the statement to be true and unprovable*, but only as a working hypothesis.
* within axiomatic arithmetic
Snorri: The Godel sentence is provably unprovable, using the axioms of arithmetic. It is also provably true, using the axioms of arithmetic plus the additional assumption that arithmetic is consistent. The proofs are in the blog post.
Steve: The Godel sentence is provably unprovable, using the axioms of arithmetic.
I could live with that (since I am more concerned with Godel’s 2nd theorem than with the 1st), were it not for what Boolos says:
if math is not a lot of bunk, then no claim of the form “claim X can’t be proved” can be proved.
Steve again: The Godel sentence […] is also provably true, using the axioms of arithmetic plus the additional assumption that arithmetic is consistent.
This I can definitely accept; but since the assumption (that arithmetic is consistent) is a working hypothesis, that leads back to my taking the truth and unprovability of the “true but unprovable” statement as a working hypothesis.
Snorri: You are right. The unprovability of the Godel sentence, as well as its truth, both require the assumption that arithmetic is consistent. I misstated this in my last comment.