I Am a Strange Loop - Douglas R. Hofstadter [88]
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,