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?
Well, suppose you wanted to know if statement X is true or false (for instance, the famous claim “Every even number greater than 2 is the sum of two primes” — which, as I stated above, remains unsettled even today, after nearly three centuries of work). You would just write X down in the formal notation of PM, then convert that formula mechanically into its Gödel number x, and feed that number into Göru (thus asking if x is prim or not). Of course x will be a huge integer, so it would probably take Göru a good while to give you an answer, but (assuming that Göru is not a hoax) sooner or later it would spit out either a “yes” or a “no”. In case Göru said “yes”, you would know that x is a prim number, which tells you that the formula it encodes is a provable formula, which means that statement X is true. Conversely, were Göru to tell you “no”, then you would know that the statement X is not provable, and so, believing in the Mathematician’s Credo (Principia Mathematica version), you would conclude it is false.
In other words, if we only had a machine that could infallibly tell apart prim numbers and “saucy” (non-prim) numbers, and taking for granted that the Principia Mathematica version of the Mathematician’s Credo is valid, then we could infallibly tell true statements from false ones. In short, having a Göru would give us a royal key to all of mathematical knowledge.
The prim numbers alone would therefore seem to contain, in a cloaked fashion, all of mathematical knowledge wrapped up inside them! No other sequence of numbers ever dreamt up by anyone before Gödel had anything like this kind of magically oracular quality. These amazing numbers seem to be worth their weight in gold! But as I told you, the prim numbers are elusive, because small ones sometimes wind up being added to the club at very late stages, so it won’t be easy to tell prim numbers from saucy ones, nor to build a Göru. (This is meant as a premonition of things to come.)
Gödelian Strangeness
Finally, Gödel carried his analogy to its inevitable, momentous conclusion, which was to spell out for his readers (not symbol by symbol, of course, but via a precise set of “assembly instructions”) an astronomically long formula of PM that made the seemingly innocent assertion, “A certain integer g is not a prim number.” However, that “certain integer g ” about which this formula spoke happened, by a most unaccidental (some might say diabolical) coincidence, to be t
he number associated with (i.e., coding for) this very formula (and so it was necessarily a gargantuan integer). As we are about to see, Gödel’s odd formula can be interpreted on two different levels, and it has two very different meanings, depending on how one interprets it.
On its more straightforward level, Gödel’s formula merely asserts that this gargantuan integer g lacks the number-theoretical property called primness. This claim is very similar to the assertion “72900 is not a prime number”, although, to be sure, g is a lot larger than 72900, and primness is a far pricklier property than is primeness. However, since primness was defined by Gödel in such a way that it numerically mirrored the provability of strings via the rules of the PM system, the formula also claims:
The formula that happens to have the code number g
is not provable via the rules of Principia Mathematica.
Now as I already said, the formula that “just happens” to have the code number g is the formula making the above claim. In short, Gödel’s formula is making a claim about itself — namely, the following claim:
This very formula is not provable via the rules of PM.
Sometimes this second phraseology is pointedly rendered as “I am not a theorem” or, even more tersely, as
I am unprovable
(where “in the PM system” is tacitly understood).
Gödel further showed that his formula, though very strange and discombobulating at first sight, was not all that unusual; indeed, it was merely one member of an infinite family of formulas that made claims about the system PM, many of which asserted (some truthfully, others falsely) similarly weird and twisty things about themselves (e.g., “Neither I nor my negation is a theorem of PM ”, “If I have a proof inside PM, then my negation has an even shorter proof than I do”, and so forth and so on).
Young Kurt Gödel — he was only 25 in 1931 — had discovered a vast sea of amazingly unsuspected, bizarrely twisty formulas hidden inside the austere, formal, type-theory-protected and therefore supposedly paradoxfree world defined by Russell and Whitehead in their grandiose threevolume œuvre Principia Mathematica, and the many counterintuitive properties of Gödel’s original formula and its countless cousins have occupied mathematicians, logicians, and philosophers ever since.
How to Stick a Formula’s Gödel Number inside the Formula
I cannot leave the topic of Gödel’s magnificent achievement without going into one slightly technical issue, because if I failed to do so, some readers would surely be left with a feeling of confusion and perhaps even skepticism about a key aspect of Gödel’s work. Moreover, this idea is actually rather magical, so it’s worth mentioning briefly.
The nagging question is this: How on earth could Gödel fit a formula’s Gödel number into the formula itself? When you think about it at first, it seems like trying to squeeze an elephant into a matchbox — and in a way, that’s exactly right. No formula can literally contain the numeral for its own Gödel number, because that numeral will contain many more symbols than the formula does! It seems at first as if this might be a fatal stumbling block, but it turns out not to be — and if you think back to our discussion of G. G. Berry’s paradox, perhaps you can see why.
The trick involves the simple fact that some huge numbers have very short descriptions (387420489, for instance, can be described in just four syllables: “nine to the ninth”). If you have a very short recipe for calculating a very long formula’s Gödel number, then instead of describing that huge number in the most plodding, clunky way (“the successor of the successor of the successor of …… the successor of the successor of zero”), you can describe it via your computational shortcut, and if you express your shortcut in symbols (rather than inserting the numeral itself) inside the formula, then you can make the formula talk about itself without squeezing an elephant into a matchbox. I won’t try to explain this in a mathematical fashion, but instead I’ll give an elegant linguistic analogy, due to the philosopher W. V. O. Quine, which gets the gist of it across.
Gödel’s Elephant-in-Matchbox Trick via Quine’s Analogy
Suppose you wanted to write a sentence in English that talks about itself without using the phrase “this sentence”. You would probably find the challenge pretty tricky, because you’d have to actually describe the sentence inside itself, using quoted words and phrases. For example, consider this first (somewhat feeble) attempt:
The sentence “This sentence has five words” has five words.
Now what I’ve just written (and you’ve just read) is a sentence that is true, but unfortunately it’s not about itself. After all, the full thing contains ten words, as well as some quotation marks. This sentence is about a shorter sentence embedded inside it, in quote marks. And changing “five” to “ten” still won’t make it refer to itself; all that this simple act does is to turn my sentence, which was true, into a false one. Take a look:
The sentence “This sentence has ten words” has ten words.
This sentence is false. And more importantly, it’s still merely about a shorter sentence embedded inside itself. As you see, so far we are not yet very close to having devised a sentence that talks about itself.
The problem is that anything I put inside quote marks will necessarily be shorter than the entire sentence of which it is a part. This is trivially obvious, and in fact it is an exact linguistic analogue to the stumbling block of trying to stick a formula’s own Gödel number directly inside the formula itself. An elephant will not fit inside a matchbox! On the other hand, an elephant’s DNA will easily fit inside a matchbox…
And indeed, just as DNA is a description of an elephant rather than the elephant itself, so there is a way of getting around the obstacle by using a description of the huge number rather than the huge number itself. (To be slightly more precise, we can use a concise symbolic description instead of using a huge numeral.) Gödel discovered this trick, and although it is quite subtle, Quine’s analogy makes it fairly easy to understand. Look at the following sentence fragment, which I’ll call “Quine’s Quasi-Quip”:
preceded by itself in quote marks yields a full sentence.
As you will note, Quine’s Quasi-Quip is certainly not a full sentence, for it has no grammatical subject (that is, “yields” has no subject); that’s why I gave it the prefix “Quasi”. But what if we were to put a noun at the head of the Quasi-Quip — say, the title “Professor Quine”? Then Quine’s Quasi-Quip will turn into a full sentence, so I’ll call it “Quine’s Quip”:
“Professor Quine” preceded by itself in quote marks yields a full sentence.
Here, the verb “yields” does have a subject — namely, Professor Quine’s title, modified by a trailing adjectival phrase that is six words long.
But what does Quine’s Quip mean? In order to figure this out, we have to actually construct the entity that it’s talking about, which means we have to precede Professor Quine’s title by itself in quote marks. This gives us:
“Professor Quine” Professor Quine
The Quine’s Quip that we created a moment ago merely asserts (or rather, claims) that this somewhat silly phrase is a full sentence. Well, that claim is obviously false. The above phrase is not a full sentence; it doesn’t even contain a verb.
However, we arbitrarily used Professor Quine’s title when we could have used a million different things. Is there some other noun that we might place at the head of Quine’s Quasi-Quip that will make Quine’s Quip come out true? What Gödel realized, and what Quine’s analogy helps to make clear, is that for this to happen, you have to use, as your subject of the verb “yields”, a subjectless sentence fragment.
What is an example of a subjectless sentence fragment? Well, just take any old sentence such as “Snow is white”, and cut off its subject. What you get is a subjectless sentence fragment: “is white”. So let’s use this as the noun to place in front of Quine’s Quasi-Quip:
“is white” preceded by itself in quote marks yields a full sentence.
This medium-sized mouthful makes a claim about a construction that we have yet to exhibit, and so let’s do so without further ado:
“is white” is white.
(I threw in the period for good measure, but let’s not quibble.)
Now what we have just produced certainly is a full sentence, because it has a verb (“is”), and that verb has a subject (the quoted phrase), and the whole thing makes sense. I’m not saying that it is true, mind you, for indeed it is blatantly false: “is white” is in fact black (although, to be fair, letters and words do contain some white space along with their black ink, otherwise we couldn’t read them). In any case, Quine’s Quasi-Quip when fed “is white” as its input yielded a full sentence, and that’s exactly what Quine’s Quip claimed. We’re definitely making headway.
The Trickiest Step
Our last devilish trick will be to use Quine’s Quasi-Quip itself as the noun to place at its head. Here, then, is Quine’s Quasi-Quip with a quoted copy of itself installed in front:
“preceded by itself in quote marks yields a full sentence”
preceded by itself in quote marks yields a full sentence.
What does this Quip claim? Well, first we have to determine what entity it is talking about, and that means we have to construct the analogue to “ ‘is white’ is white”. Well, in this case, the analogue is the following:
“preceded by itself in quote marks yields a full sentence”
preceded by itself in quote marks yields a full sentence.
I hope you are not lost at this point, for we really have hit the crux of the matter. Quine’s Quip turns out to be talking about a phrase that is identical to the Quip itself! It is claiming that something is a full sentence, and when you go about constructing that thing, it turns out to be Quine’s Quip itself. So Quine’s Quip talks about itself, claiming of itself that it is a full sentence (which it surely is, even though it is built out of two subjectless sentence fragments, one in quote marks and one not).
I Am a Strange Loop Page 20