I Am a Strange Loop - Douglas R. Hofstadter [91]
“when fed its own Gödel number yields a non-prim number”
when fed its own Gödel number yields a non-prim number.
The above sentence is neither fish nor fowl, for it is not a formula of Principia Mathematica but an English sentence, so of course it doesn’t have a Gödel number and it couldn’t possibly be a theorem (or a nontheorem) of PM. What a mixed metaphor!
And yet, mixed metaphor though it is, it still does a pretty decent job of getting across the flavor of the PM formula that Gödel actually concocted. You just have to keep in mind that using quote marks is a metaphor for taking Gödel numbers, so the upper line should be thought of as being a Gödel number (k) rather than as being a sentence fragment in quote marks. This means that metaphorically, the lower line (an English sentence fragment) has been fed its own Gödel number as its subject. Very cute!
I know that this is very tricky, so let me state it once again, slightly differently. Gödel asks you to imagine the formula that k stands for (that formula happens to contain the variable x), and then to feed k into it (this means to replace the single letter x by the extremely long numeral k, thus giving you a much bigger formula than you started with), and to take the Gödel number of the result. That will be the number g, huger far than k — and lastly, Gödel asserts that this walloping number is not a prim number. If you’ve followed my hand-waving argument, you will agree that the full formula’s Gödel number (g) is not found explicitly inside the formula, but instead is very subtly described by the formula. The elephant’s DNA has been used to get a description of the entire elephant into the matchbox.
Sluggo and the Morton Salt Girl
Well, I don’t want to stress the technical points here. The main thing to remember is that Gödel devised a very clever number-description trick — a recipe for making a very huge number g out of a less huge number k — in order to get a formula of PM to make a claim about its own Gödel number’s non-primness (which means that the formula is actually making a claim of its own nontheoremhood). And you might also try to remember that the “little” number k is the Gödel number of a “formula fragment” containing a variable x, analogous to a subjectless sentence fragment in quote marks, while the larger number g is the Gödel number of a complete sentence in PM notation, analogous to a complete sentence in English.
Popular culture is by no means immune to the delights of self-reference, and it happens that the two ideas we have been contrasting here — having a formula contain its own Gödel number directly (which would necessitate an infinite regress) and having a formula contain a description of its Gödel number (which beautifully bypasses the infinite regress) — are charmingly illustrated by two images with which readers may be familiar.
In this first image, Ernie Bushmiller’s character Sluggo (from his classic strip Nancy) is dreaming of himself dreaming of himself dreaming of himself, without end. It is clearly a case of self-reference, but it involves an infinite regress, analogous to a PM formula that contained its own Gödel number directly. Such a formula, unfortunately, would have to be infinitely long!
Our second image, in contrast, is the famous label of a Morton Salt box, which shows a girl holding a box of Morton Salt. You may think you smell infinite regress once again, but if so, you are fooling yourself! The girl’s arm is covering up the critical spot where the regress would occur. If you were to ask the girl to (please) hand you her salt box so that you could actually see the infinite regress on its label, you would wind up disappointed, for the label on that box would show her holding a yet smaller box with her arm once again blocking the regress.
And yet we still have a self-referential picture, because customers in the grocery store understand that the little box shown on the label is the same as the big box they are holding.