I Am a Strange Loop

Indeed, reader, let’s posit, you and I, that KG is provable in PM, and then see where this assumption — I’ll dub it the “Provable-KG Scenario” — leads us. The ironic thing, please note, is that KG itself doesn’t believe the Provable-KG Scenario. Perversely, KG shouts to the world, “I am not provable!” So if we are right about KG, dear reader, then KG is wrong about itself, no matter how loudly it shouts. After all, no formula can be both provable (as we claim KG is) and also unprovable (as KG claims to be). One of us has to be wrong. (And for any formula, being wrong means being false. The two terms are synonyms.) So… if the Provable-KG Scenario is the case, then KG is wrong (= false).

All right. Our reasoning started with the Provable-KG Scenario and wound up with the conclusion “KG is false”. In other words, if KG is provable, then it is also false. But hold on, now — a provable falsity in PM?! Didn’t we just declare firmly, a few moments ago, that PM never proves falsities? Yes, we did. We agreed with the universal logicians’ belief that PM is consistent. If we stick to our guns, then, the Provable-KG Scenario has to be wrong, because it leads to Russell’s worst nightmare. We have to retract it, cancel it, repudiate it, nullify it, and revoke it, because accepting it led us to a conclusion (“PM is inconsistent”) that we know is wrong.

Ergo, the Provable-KG Scenario is hereby rejected, which leaves us with the opposite scenario: KG is not provable. Now the funny thing is that this is exactly what KG is shouting to the rooftops. We see that what KG proclaims about itself — “I’m unprovable!” — is true. In a nutshell, we have established two facts: (1) KG is unprovable in PM; and (2) KG is true.

We have just uncovered a very strange anomaly inside PM: here is a statement of arithmetic (or number theory, to be slightly more precise) that we are sure is true, and yet we are equally sure it is unprovable — and to cap it off, these two contradictory-sounding facts are consequences of each other! In other words, KG is unprovable not only although it is true, but worse yet, because it is true.

This weird situation is utterly unprecedented and profoundly perverse. It flies in the face of the Mathematician’s Credo, which asserts that truth and provability are just two sides of the same coin — that they always go together, because they entail each other. Instead, we’ve just encountered a case where, astoundingly, truth and unprovability entail each other. Now isn’t that a fine how-do-you-do?

Incompleteness Derives from Strength

The fact that there exists a truth of number theory that is unprovable in PM means, as you may recall from Chapter 9, that PM is incomplete. It has holes in it. (So far we’ve seen just one hole — KG — but it turns out there are plenty more — an infinity of them, in fact.) Some statements of number theory that should be provable escape from PM’s vast net of proof — they slip through its mesh. Clearly, this is another kind of nightmare — perhaps not quite as devastating as Bertrand Russell’s worst nightmare, but somehow even more insidious and troubling.

Such a state of affairs is certainly not what the mathematicians and logicians of 1931 expected. Nothing in the air suggested that the axioms and rules of inference of Principia Mathematica were weak or deficient in any way. They seemed, quite the contrary, to imply virtually everything that anyone might have thought was true about numbers. The opening lines of Gödel’s 1931 article, quoted in Chapter 10, state this clearly. If you’ll recall, he wrote, speaking of Principia Mathematica and Zermelo-Fraenkel set theory: “These two systems are so extensive that all methods of proof used in mathematics today have been formalized in them, i.e., reduced to a few axioms and rules of inference.”

What Gödel articulates here was virtually a universal credo at the time, and so his revelation of PM’s incompleteness, in the twenty-five pages that followed, came like a sudden thunderbolt from the bluest of skies.

To add insult to injury, Gödel’s conclusion sprang not from a weakness in PM but from a strength. That strength is the fact that numbers are so flexible or “chameleonic” that their patterns can mimic patterns of reasoning. Gödel exploited the simple but marvelous fact that the familiar whole numbers can dance in just the same way as the unfamiliar symbolpatterns of PM dance. More specifically, the prim numbers that he invented act indistinguishably from provable strings, and one of PM’s natural strengths is that it is able to talk about prim numbers. For this reason, it is able to talk about itself (in code). In a word, PM’s expressive power is what gives rise to its incompleteness. What a fantastic irony!