Douglas Hofstadter - I Am a Strange Loop

Why would logicians and mathematicians — not just Russell but all of them (including Gödel) — give such good odds for this? Well, the axioms of PM are certainly true, and its rules of inference are as simple and as rock-solidly sane as anything one could imagine. How can you get falsities out of that? To think that PM might have false theorems is, quite literally, as hard as thinking that two plus two is five. And so, along with all mathematicians and logicans, let’s give Russell and Whitehead the benefit of the doubt and presume that their grand palace of logic is consistent. From here on out, then, we’ll generously assume that PM never proves any false statements — all of its theorems are sure to be true statements. Now then, armed with our friendly assumption, let’s ask ourselves, “What would follow if KG were provable inside PM ?”

A Strange Land where “Because” Coincides with “Although”

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 un provability 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!

Bertrand Russell’s Second-worst Nightmare

Any enrichment of PM (say, a system having more axioms or more rules of inference, or both) would have to be just as expressive of the flexibility of numbers as was PM (otherwise it would be weaker, not stronger), and so the same Gödelian trap would succeed in catching it — it would be just as readily hoist on its own petard.

Let me spell this out more concretely. Strings provable in the larger and allegedly superior system Super-PM would be isomorphically imitated by a richer set of numbers than the prim numbers (hence let’s call them “super-prim numbers”). At this point, just as he did for PM, Gödel would promptly create a new formula KH for Super-PM that said, “The number h is not a super-prim number”, and of course he would do it in such a way that h would be the Gödel number of KH itself. (Doing this for Super-PM is a cinch once you’ve done it for PM. ) The exact same pattern of reasoning that we just stepped through for PM would go through once again, and the supposedly more powerful system would succumb to incompleteness in just the same way, and for just the same reasons, as PM did. The old proverb puts it succinctly: “The bigger they are, the harder they fall.”

In other words, the hole in PM (and in any other axiomatic system as rich as PM ) is not due to some careless oversight by Russell and Whitehead but is simply an inevitable property of any system that is flexible enough to capture the chameleonic quality of whole numbers. PM is rich enough to be able to turn around and point at itself, like a television camera pointing at the screen to which it is sending its image. If you make a good enough TV system, this looping-back ability is inevitable. And the higher the system’s resolution is, the more faithful the image is.