I Am a Strange Loop (29 page)

The decoding process works by finding the prime factorization of 72900 (which is unique), and reading off the exponents that the ascending primes are raised to, one by one — 2, 6, 2 in this case.

To summarize, then, in this non-obvious but simple manner, Gödel had found a way to replace any given formula of
PM
by an equivalent number (which other people soon would dub its
Gödel number
). He then extended this idea of “arithmetization” to cover arbitrary
sequences
of formulas, since proofs in
PM
are sequences of formulas, and he wanted to be able to deal with proofs, not just isolated formulas. Thus an arbitrarily long sequence of formulas could be converted into one large integer via essentially the same technique, using primes and exponents. You can imagine that we’re talking
really
big numbers here.

In short, Gödel showed how any visual symbol-pattern whatsoever in the idiosyncratic notation of
Principia Mathematica
could be assigned a unique number, which could easily be decoded to give back the visual pattern (
i.e.,
sequence of symbols) to which it corresponded. Conceiving of and polishing this precise two-way mapping, now universally called “Gödel numbering”, constituted the first key step of Gödel’s work.

Very Big Integers Moving in Lock-step with Formulas

The next key step was to make Fibonacci-like recursive definitions of special sets of integers — integers that would organically grow out of previously generated ones by addition or multiplication or more complex computations. One example would be the
wff
numbers, which are those integers that, via Gödel’s code, represent “well-formed” or “meaningful” formulas of
PM,
as opposed to those that represent meaningless or ungrammatical strings. (A sample well-formed formula, or “wff ” for short, would be “0+0=sss0”. Though it asserts a falsity, it’s still a meaningful statement. On the other hand, “=)0(=” and “00==0+=” are not wffs. Like the arbitrary sequence of pseudo-words “zzip dubbiwubbi pizz”, they don’t assert anything.) Since, as it happens, longer wffs are built up in
PM
from shorter wffs by just a few simple and standard rules of typographical juxtaposition, their larger code numbers can likewise be built up from the smaller code numbers of shorter ones by just a few simple and standard rules of numerical calculation.

I’ve said the foregoing rather casually, but in fact this step was perhaps the deepest of Gödel’s key insights — namely, that once strings of symbols had been “arithmetized” (given numerical counterparts), then any kind of rule-based typographical shunting-around of strings on paper could be perfectly paralleled by some kind of
purely arithmetical calculation
involving their numerical proxies — which were huge numbers, to be sure, but still just numbers. What to Russell and Whitehead looked like elaborate
symbol-shunting
looked like a lot of straightforward
number-crunching
to Kurt Gödel (although of course he didn’t use that colorful modern term, since this was all taking place back in the prehistoric days when computers didn’t yet exist). These were simply two different views of what was going on — views that were 100 percent equivalent and interchangeable.

Glimmerings of How PM Can Twist Around and See Itself

Gödel saw that the game of building up an infinite class of numbers, such as wff numbers, through recursion — that is, making new “members of the club” by combining older, established members via some number-crunching rule — is essentially the same idea as Fibonacci’s recursive game of building up the class of
F
numbers by taking sums of earlier members. Of course recursive processes can be far more complicated than just taking the sum of the latest two members of the club.

What a recursive definition does, albeit implicitly, is to divide the entire set of integers into members and non-members of the club — that is, those numbers that are
reachable,
sooner or later, via the recursive building-up process, and those that are
never reachable,
no matter how long one waits. Thus 34 is a member of the
F
club, whereas 35 is a non-member. How do we know 35 is not an
F
number? That’s very easy — the rule that makes new
F
numbers always makes larger ones from smaller ones, and so once we’ve passed a certain size, there’s no chance we’ll be returning to “pick up” other numbers in that vicinity later. In other words, once we’ve made the
F
numbers 1, 2, 3, 5, 8, 13, 21, 34, 55, we know they are the only ones in that range, so obviously 35, 36, and so on, up to 54, are not
F
numbers.

If, however, some other club of numbers is defined by a recursive rule whose outputs are sometimes
bigger
than its inputs and other times are
smaller
than its inputs, then, in contrast to the simple case of the
F
club, you can’t be so sure that you won’t ever be coming back and picking up smaller integers that were missed in earlier passes.

Let’s think a little bit more about the recursively defined club of numbers that we called “wff numbers”. We’ve seen that the number 72900 possesses “wff-ness”, and if you think about it, you can see that 576 and 2916 lack that quality. (Why? Well, if you factor them and look at the exponents of 2 and 3, you will see that these numbers are the numerical encodings of the strings “0=” and “=0”, respectively, neither of which makes sense, whence they are not well-formed formulas.) In other words, despite its odd definition, wff-ness, no more and no less than squareness or primeness or Fibonacci’s
F
-ness, is a valid object of study in the world of pure number. The distinction between members and non-members of the “wff club” is every bit as genuine a
number-theoretical
distinction as that between members and non-members of the club of squares, the club of prime numbers, or the club of
F
numbers, for wff numbers are definable in a recursive arithmetical (
i.e.,
computational) fashion. Moreover, it happens that the recursive rules defining wff-ness always produce outputs that are bigger than their inputs, so that wff-ness shares with
F
-ness the simple property that once you’ve exceeded a certain magnitude, you know you’ll never be back visiting that zone again.

Just as some people’s curiosity was fired by the fact of seeing a square in Fibonacci’s recursively defined sequence, so some people might become interested in the question as to whether there are any squares (or cubes, etc.) in the recursively defined sequence of wff numbers. They could spend a lot of time investigating such purely number-theoretical questions, never thinking at all about the corresponding formulas of
Principia Mathematica.

One could be completely ignorant of the fact that Gödel’s wff numbers had their origin in Russell and Whitehead’s rules defining well-formedness in
Principia Mathematica,
just as one can study the laws of probability without ever suspecting that this deep branch of mathematics was originally developed to analyze gambling. What long ago inspired someone to dream up a particular recursive definition obviously doesn’t affect the numbers it defines; all that matters is that there should be a purely computational way of making any member of the club grow out of the initial seeds by applying the rules some finite number of times.

Now wff numbers are, as it happens, relatively easy to define in a recursive fashion, and for that reason wff-ness (exactly like
F-
ness) is just the kind of mathematical notion that
Principia Mathematica
was designed to study. To be sure, Whitehead and Russell had never dreamed that their mechanical reasoning system might be put to such a curious use, in which its own properties as a machine were essentially placed under observation by itself, rather like using a microscope to examine some of its own lenses for possible defects. But then, inventions often do surprise their inventors.

Prim Numbers

Having realized that some hypothetical volume of the series by Whitehead and Russell could define and systematically explore the various numerical properties of wff numbers, Gödel pushed his analogy further and showed, with a good deal of fancy machinery but actually not very much conceptual difficulty, that there was an infinitely more interesting recursively defined class of whole numbers, which I shall here call
prim
numbers (whimsically saluting the title of the famous three tomes), and which are the numbers belonging to
provable
formulas of
PM
(
i.e.,
theorems).

A
PM
proof, of course, is a series of formulas leading from the axioms of
PM
all the way to the formula in question, each step being allowed by some rule of reasoning, which in
PM
became a formal typographical rule of inference. To every typographical rule of inference acting on strings of
PM,
Gödel exhibited a perfectly matching computational rule that acted on numbers. Numerical computation was effectively thumbing its nose at typographical manipulation, sassily saying, “Anything you can do, I can do better!” Well, not really
better
— but the key point, as Gödel showed beyond any doubt, was that a computational rule would always be able to mimic perfectly — to keep in perfect synchrony with — any formal typographical rule, and so numerical rules were
just as good.

The upshot was that to every
provable string
of Russell and Whitehead’s formal system, there was a counterpart
prim number.
Any integer that was prim could be decoded into symbols, and the string you got would be a provable-in-
PM
formula. Likewise, any provable-in-
PM
formula could be encoded as one whopping huge integer, and by God, with enough calculation, you could show that that number was a prim number. A simple example of a prim number is, once again, our friend 72900, since the formula “0=0”, over and above being a well-formed formula, is also, and not too surprisingly, derivable in
PM.
(Indeed, if it weren’t,
PM
would be absolutely pathetic as a mechanical model of mathematical reasoning!)

There is a crucial difference between wff numbers and prim numbers, which comes from the fact that the rules of inference of
PM
sometimes produce output strings that are
shorter
than their input strings. This means that the corresponding arithmetical rules defining prim numbers will sometimes take
large
prim numbers as input and make from them a
smaller
prim number as output. Therefore, stretches of the number line that have been visited once can always be revisited later, and this fact makes it much, much harder to determine about a given integer whether it is prim or not. This is a central and very deep fact about prim numbers.

Just as with squares, primes,
F
numbers, or wff numbers, there could once again be a hypothetical volume of the series of tomes by Whitehead and Russell in which prim numbers were defined and their mathematical properties studied. For example, such a volume might contain a proof of the formula of
PM
that (when examined carefully) asserts “72900 is a prim number”, and it might also discuss another formula that could be seen to assert the opposite (“72900 is
not
a prim number”), and so on. This latter statement is false, of course, while the former one is true. And even more complex number-theoretical ideas could be expressed using the
PM
notation and discussed in the hypothetical volume, such as “There are infinitely many prim numbers” — which would be tantamount to asserting (via a code), “There are infinitely many formulas that are provable in
PM
”
.

Although it might seem an odd thing to do, one could certainly pose eighteenth-century–style number-theory questions such as, “Which integers are expressible as the sum of two prim numbers, and which integers are not?” Probably nobody would ever seriously ask such an oddball question, but the point is that the property of being a prim number, although it’s a rather arcane “modern” property, is no more and no less a genuinely number-theoretical property of an integer than is a “classical” property, such as being square or being prime or being a Fibonacci number.

The Uncanny Power of Prim Numbers

Suppose someone told you that they had built a machine — I’ll dub it “Guru” — that would always correctly answer any question of the form “Is
n
a prime number?”, with
n
being any integer that you wish. When asked, “Is 641 prime?”, Guru would spin its wheels for a bit and then say “yes”. As for 642, Guru would “think” a little while and then say “no”. I suppose you would not be terribly surprised by such a machine. That such a machine can be realized, either in silicon circuitry on in domino-chain technology, is not anything to boggle anyone’s mind in this day and age.

But suppose someone told you that they had built an analogous machine — I’ll dub it “Göru” — that would always correctly answer any question of the form “Is
n
a prim number?” Would this claim — strictly analogous to the previous one — strike you as equally ho-hum? If so, then I respectfully submit that you’ve got another think coming.

The reason is this. If you believed Göru to be reliable and you also believed in the Mathematician’s Credo (
Principia Mathematica
version), then you could conclude that your little Göru, working all by itself, could answer
any number-theoretical question
that you were interested in, just like a genie conjured from a magic lamp. How so? What makes Göru a magic genie?