I Am a Strange Loop

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 Goru to be reliable and you also believed in the Mathematician’s Credo (Principia Mathematica version), then you could conclude that your little Goru, 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 Goru 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 Godel number x, and feed that number into Goru (thus asking if x is prim or not). Of course x will be a huge integer, so it would probably take Goru a good while to give you an answer, but (assuming that Goru is not a hoax) sooner or later it would spit out either a “yes” or a “no”. In case Goru 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 Goru 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 Goru 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 Godel 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 Goru. (This is meant as a premonition of things to come.)

Godelian Strangeness

Finally, Godel 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 the number associated with (i.e., coding for) this very formula (and so it was necessarily a gargantuan integer). As we are about to see, Godel’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, Godel’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 Godel 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, Godel’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).

Godel 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 Godel — 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 Godel’s original formula and its countless cousins have occupied mathematicians, logicians, and philosophers ever since.

How to Stick a Formula’s Godel Number inside the Formula

I cannot leave the topic of Godel’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 Godel’s work. Moreover, this idea is actually rather magical, so it’s worth mentioning briefly.

The nagging question is this: How on earth could Godel fit a formula’s Godel 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 Godel 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 Godel 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.

Godel’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