I Am a Strange Loop (35 page)

What, then, would Bertrand Russell’s worst nightmare be? It would be that someday, someone would come up with a
PM
proof of a formula expressing an untrue arithmetical statement (“0 = s0” is a good example), because the moment that that happened,
PM
would be fit for the dumpster. Luckily for Russell, however, every logician on earth would give you better odds for a snowball’s surviving a century in hell. In other words, Bertrand Russell’s worst nightmare is truly just a nightmare, and it will never take place outside of dreamland.

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.

As in judo, your opponent’s power is the source of their vulnerability. Kurt Gödel, maneuvering like a black belt, used
PM
’s power to bring it crashing down. Not as catastrophically as with inconsistency, mind you, but in a wholly unanticipated fashion — crashing down with
incompleteness.
The fact that you can’t get around Gödel’s black-belt trickery by enriching or enlarging
PM
in any fashion is called “essential incompleteness” — Bertrand Russell’s
second-worst
nightmare. But unlike his worst nightmare, which is just a bad dream, this nightmare takes place outside of dreamland.

An Endless Succession of Monsters

Not only does extending
PM
fail to save the boat from sinking, but worse, KG is far from being the only hole in
PM.
There are infinitely many ways of Gödel-numbering any given axiomatic system, and each one produces its own cousin to KG. They’re all different, but they’re so similar they are like clones. If you set out to save the sinking boat, you are free to toss KG or any of its clones as a new axiom into
PM
(for that matter, feel free to toss them all in at once!), but your heroic act will do little good; Gödel’s recipe will instantly produce a brand-new cousin to KG. Once again, this new self-referential Gödelian string will be “just like” KG and its passel of clones, but it won’t be
identical
to any of them. And you can toss
that
one in as well, and you’ll get yet another cousin! It seems that holes are popping up inside the struggling boat of
PM
as plentifully as daisies and violets pop up in the springtime. You can see why I call this nightmare more insidious and troubling than Russell’s worst one.

Not only Bertrand Russell was blindsided by this amazingly perverse and yet stunningly beautiful maneuver; virtually every mathematical thinker was, including the great German mathematician David Hilbert, one of whose major goals in life had been to rigorously ground all of mathematics in an axiomatic framework (this was called “the Hilbert Program”). Up till the Great Thunderclap of 1931, it was universally believed that this noble goal had been reached by Whitehead and Russell.

To put it another way, the mathematicians of that time universally believed in what I earlier called the “Mathematician’s Credo (
Principia Mathematica
version)”. Gödel’s shocking revelation that the pedestal upon which they had quite reasonably placed their faith was fundamentally and irreparably flawed followed from two things. One is our kindly assumption that the pedestal is consistent (
i.e.,
we will never find any falsity lurking among the theorems of
PM
); the other is the nonprovability in
PM
of KG and all its infinitely many cousins, which we just showed is a consequence flowing from their self-referentiality, taking
PM
’s consistency into account.

To recap it just one last time, what is it about KG (or any of its cousins) that makes it not provable? In a word, it is its self-referential meaning: if KG were provable, its loopy meaning would flip around and make it unprovable, and so
PM
would be inconsistent, which we know it is not.

But notice that we have not made any detailed analysis of the nature of derivations that would try to make KG appear as their bottom line. In fact, we have totally ignored the
Russellian
meaning of KG (what I’ve been calling its
primary
meaning), which is the claim that the gargantuan number that I called
‘g’
possesses a rather arcane and recherché number-theoretical property that I called “sauciness” or “non-primness”
.
You’ll note that in the last couple of pages, not one word has appeared about prim numbers or non-prim numbers and their number-theoretical properties, nor has the number
g
been mentioned at all. We finessed all such numerical issues by looking only at KG’s
secondary
meaning, the meaning that Bertrand Russell never quite got. A few lines of purely non-numerical reasoning (the second section of this chapter) convinced us that this statement (which is about numbers) could not conceivably be a theorem of
PM.

Consistency Condemns a Towering Peak to Unscalability

Imagine that a team of satellite-borne explorers has just discovered an unsuspected Himalayan mountain peak (let’s call it “KJ”) and imagine that they proclaim, both instantly and with total confidence, that thanks to a special, most unusual property of the summit alone, there is no conceivable route leading up to it. Merely from looking at a single photo shot vertically downwards from 250 miles up, the team declares KJ an
unclimbable peak,
and they reach this dramatic conclusion without giving any thought to the peak’s properties as seen from a conventional mountaineering perspective, let alone getting their hands dirty and actually trying out any of the countless potential approaches leading up the steep slopes towards it. “Nope, none of them will work!”, they cheerfully assert. “No need to bother trying any of them out — you’ll fail every time!”