I Am a Strange Loop

by Douglas R. Hofstadter

  In other words, the hole in PM (and in any other axiomatic system as rich as PM) is not due to some careless oversight by Russell and Whitehead but is simply an inevitable property of any system that is flexible enough to capture the chameleonic quality of whole numbers. PM is rich enough to be able to turn around and point at itself, like a television camera pointing at the screen to which it is sending its image. If you make a good enough TV system, this looping-back ability is inevitable. And the higher the system’s resolution is, the more faithful the image is.

  As in judo, your opponent’s power is the source of their vulnerability. Kurt Gödel, maneuvering like a black belt, used PM’s power to bring it crashing down. Not as catastrophically as with inconsistency, mind you, but in a wholly unanticipated fashion — crashing down with incompleteness. The fact that you can’t get around Gödel’s black-belt trickery by enriching or enlarging PM in any fashion is called “essential incompleteness” — Bertrand Russell’s second-worst nightmare. But unlike his worst nightmare, which is just a bad dream, this nightmare takes place outside of dreamland.

  An Endless Succession of Monsters

  Not only does extending PM fail to save the boat from sinking, but worse, KG is far from being the only hole in PM. There are infinitely many ways of Gödel-numbering any given axiomatic system, and each one produces its own cousin to KG. They’re all different, but they’re so similar they are like clones. If you set out to save the sinking boat, you are free to toss KG or any of its clones as a new axiom into PM (for that matter, feel free to toss them all in at once!), but your heroic act will do little good; Gödel’s recipe will instantly produce a brand-new cousin to KG. Once again, this new self-referential Gödelian string will be “just like” KG and its passel of clones, but it won’t be identical to any of them. And you can toss that one in as well, and you’ll get yet another cousin! It seems that holes are popping up inside the struggling boat of PM as plentifully as daisies and violets pop up in the springtime. You can see why I call this nightmare more insidious and troubling than Russell’s worst one.

  Not only Bertrand Russell was blindsided by this amazingly perverse and yet stunningly beautiful maneuver; virtually every mathematical thinker was, including the great German mathematician David Hilbert, one of whose major goals in life had been to rigorously ground all of mathematics in an axiomatic framework (this was called “the Hilbert Program”). Up till the Great Thunderclap of 1931, it was universally believed that this noble goal had been reached by Whitehead and Russell.

  To put it another way, the mathematicians of that time universally believed in what I earlier called the “Mathematician’s Credo (Principia Mathematica version)”. Gödel’s shocking revelation that the pedestal upon which they had quite reasonably placed their faith was fundamentally and irreparably flawed followed from two things. One is our kindly assumption that the pedestal is consistent (i.e., we will never find any falsity lurking among the theorems of PM); the other is the nonprovability in PM of KG and all its infinitely many cousins, which we just showed is a consequence flowing from their self-referentiality, taking PM’s consistency into account.

  To recap it just one last time, what is it about KG (or any of its cousins) that makes it not provable? In a word, it is its self-referential meaning: if KG were provable, its loopy meaning would flip around and make it unprovable, and so PM would be inconsistent, which we know it is not.

  But notice that we have not made any detailed analysis of the nature of derivations that would try to make KG appear as their bottom line. In fact, we have totally ignored the Russellian meaning of KG (what I’ve been calling its primary meaning), which is the claim that the gargantuan number that I called ‘g’ possesses a rather arcane and recherché number-theoretical property that I called “sauciness” or “non-primness”. You’ll note that in the last couple of pages, not one word has appeared about prim numbers or non-prim numbers and their number-theoretical properties, nor has the number g been mentioned at all. We finessed all such numerical issues by looking only at KG’s secondary meaning, the meaning that Bertrand Russell never quite got. A few lines of purely non-numerical reasoning (the second section of this chapter) convinced us that this statement (which is about numbers) could not conceivably be a theorem of PM.

  Consistency Condemns a Towering Peak to Unscalability

  Imagine that a team of satellite-borne explorers has just discovered an unsuspected Himalayan mountain peak (let’s call it “KJ”) and imagine that they proclaim, both instantly and with total confidence, that thanks to a special, most unusual property of the summit alone, there is no conceivable route leading up to it. Merely from looking at a single photo shot vertically downwards from 250 miles up, the team declares KJ an unclimbable peak, and they reach this dramatic conclusion without giving any thought to the peak’s properties as seen from a conventional mountaineering perspective, let alone getting their hands dirty and actually trying out any of the countless potential approaches leading up the steep slopes towards it. “Nope, none of them will work!”, they cheerfully assert. “No need to bother trying any of them out — you’ll fail every time!”

  Were such an odd event to transpire, it would be remarkably different from how all previous conclusions about the scalability of mountains had been reached. Heretofore, climbers always had to attempt many routes — indeed, to attempt them many times, with many types of equipment and in diverse weather conditions — and even thousands of failures in a row would not constitute an ironclad proof that the given peak was forever unscalable; all one could conclude would be that it had so far resisted scaling. Indeed, the very idea of a “proof of unscalability” would be most alien to the activity of mountaineering.

  By contrast, our team of explorers has concluded from some novel property of KJ, without once thinking about (let alone actually trying out) a single one of the infinitely many conceivable routes leading up to its summit, that by its very nature it is unscalable. And yet their conclusion, they claim, is not merely probable or extremely likely, but dead certain.

  This amounts to an unprecedented, upside-down, top-down kind of alpinistic causality. What kind of property might account for the peculiar peak’s unscalability? Traditional climbing experts would be bewildered at a blanket claim that for every conceivable route, climbers will inevitably encounter some fatal obstacle along the way. They might more modestly conclude that the distant peak would be extremely difficult to scale by looking upwards at it and trying to take into account all the imaginable routes that one might take in order to reach it. But our intrepid team, by contrast, has looked solely at KJ’s tippy-top and concluded downwards that there simply could be no route that would ever reach it from below.

  When pressed very hard, the team of explorers finally explains how they reached their shattering conclusions. It turns out that the photograph taken of KJ from above was made not with ordinary light, which would reveal nothing special at all, but with the newly discovered “Gödel rays”. When KJ is perceived through this novel medium, a deeply hidden set of fatal structures is revealed.

  The problem stems from the consistency of the rock base underlying the glaciers at the very top; it is so delicate that, were any climber to come within striking distance of the peak, the act of setting the slightest weight on it (even a grain of salt; even a baby bumblebee’s eyelash!) would instantly trigger a thunderous earthquake, and the whole mountain would come tumbling down in rubble. So the peak’s inaccessibility turns out to have nothing to do with how anyone might try to get up to it; it has to do with an inherent instability belonging to the summit itself, and moreover, a type of instability that only Gödel rays can reveal. Quite a silly fantasy, is it not?

  Downward Causality in Mathematics

  Indeed it is. But Kurt Gödel’s bombshell, though just as fantastic, was not a fantasy. It was rigorous and precise. It revealed the stunning fact that a formula’s hidden meaning may have a peculiar kind of “downward” causal power, determining the for
mula’s truth or falsity (or its derivability or nonderivability inside PM or any other sufficiently rich axiomatic system). Merely from knowing the formula’s meaning, one can infer its truth or falsity without any effort to derive it in the old-fashioned way, which requires one to trudge methodically “upwards” from the axioms.

  This is not just peculiar; it is astonishing. Normally, one cannot merely look at what a mathematical conjecture says and simply appeal to the content of that statement on its own to deduce whether the statement is true or false (or provable or unprovable).

  For instance, if I tell you, “There are infinitely many perfect numbers” (numbers such as 6, 28, and 496, whose factors add up to the number itself), you will not know if my claim — call it ‘Imp’ — is true or not, and merely staring for a long time at the written-out statement of Imp (whether it’s expressed in English words or in some prickly formal notation such as that of PM) will not help you in the least. You will have to try out various approaches to this peak. Thus you might discover that 8128 is the next perfect number after 496; you might note that none of the perfect numbers you come up with is odd, which is somewhat odd; you might observe that each one you find has the form p(p+1)/2, where p is an odd prime (such as 3, 7, or 31) and p+1 is also a power of 2 (such as 4, 8, or 32); and so forth.

  After a while, perhaps a long series of failures to prove Imp would gradually bring you around to suspecting that it is false. In that case, you might decide to switch goals and try out various approaches to the nearby rival peak — namely, Imp’s negation ∼ Imp — which is the statement “There are not infinitely many perfect numbers”, which is tantamount to asserting that there is a largest perfect number (reminiscent of our old friend P, allegedly the largest prime number in the world).

  But suppose that through a stunning stroke of genius you discovered a new kind of “Gödel ray” (i.e., some clever new Gödel numbering, including all of the standard Gödel machinery that makes prim numbers dance in perfect synchrony with provable strings) that allowed you to see through to a hidden second level of meaning belonging to Imp — a hidden meaning that proclaimed, to those lucky few who knew how to decipher it, “The integer i is not prim”, where i happened to be the Gödel number of Imp itself. Well, dear reader, I suspect it wouldn’t take you long to recognize this scenario. You would quickly realize that Imp, just like KG, asserts of itself via your new Gödel code, “Imp has no proof in PM.”

  In that most delightful though most unlikely of scenarios, you could immediately conclude, without any further search through the world of whole numbers and their factors, or through the world of rigorous proofs, that Imp was both true and unprovable. In other words, you would conclude that the statement “There are infinitely many perfect numbers” is true, and you would also conclude that it has no proof using PM’s axioms and rules of inference, and last of all (twisting the knife of irony), you would conclude that Imp’s lack of proof in PM is a direct consequence of its truth.

  You may think the scenario I’ve just painted is nonsensical, but it is exactly analogous to what Gödel did. It’s just that instead of starting with an a priori well-known and interesting statement about numbers and then fortuitously bumping into a very strange alternate meaning hidden inside it, Gödel carefully concocted a statement about numbers and revealed that, because of how he had designed it, it had a very strange alternate meaning. Other than that, though, the two scenarios are identical.

  The hypothetical Imp scenario and the genuine KG scenario are, as I’m sure you can tell, radically different from how mathematics has traditionally been done. They amount to upside-down reasoning — reasoning from a would-be theorem downwards, rather than from axioms upwards, and in particular, reasoning from a hidden meaning of the would-be theorem, rather than from its surface-level claim about numbers.

  Göru and the Futile Quest for a Truth Machine

  Do you remember Göru, the hypothetical machine that tells prim numbers from saucy (non-prim) numbers? Back in Chapter 10, I pointed out that if we had built such a Göru, or if someone had simply given us one, then we could determine the truth or falsity of any number-theoretical conjecture at all. To do so, we would merely translate conjecture C into a PM formula, calculate its Gödel number c (a straightforward task), and then ask Göru, “Is c prim or saucy?” If Göru came back with the answer “c is prim”, we’d proclaim, “Since c is prim, conjecture C is provable, hence it is true”, whereas if Göru came back with the answer “c is saucy”, then we’d proclaim, “Since c is saucy, conjecture C is not provable, hence it is false.” And since Göru would always (by stipulation) eventually give us one or the other of these answers, we could just sit back and let it solve whatever math puzzle we dreamt up, of whatever level of profundity.

  It’s a great scenario for solving all problems with just one little gadget, but unfortunately we can now see that it is fatally flawed. Gödel revealed to us that there is a profound gulf between truth and provability in PM (indeed, in any formal axiomatic system like PM). That is, there are many true statements that are not provable, alas. So if a formula of PM fails to be a theorem, you can’t take that as a sure sign that it is false (although luckily, whenever a formula is a theorem, that’s a sure sign that it is true). So even if Göru works exactly as advertised, always giving us a correct ‘yes’ or ‘no’ answer to any question of the form “Is n prim?”, it won’t be able to answer all mathematical questions for us, after all.

  Despite being less informative than we had hoped, Göru would still be a nice machine to own, but it turns out that even that is not in the cards. No reliable prim/saucy distinguisher can exist at all. (I won’t go into the details here, but they can be found in many texts of mathematical logic or computability.) All of a sudden, it seems as if dreams are coming crashing down all around us — and in a sense, this is what happened in the 1930’s, when the great gulf between the abstract concept of truth and mechanical ways to ascertain truth was first discovered, and the stunning size of this gulf started to dawn on people.

  It was logician Alfred Tarski who put one of the last nails in the coffin of mathematicians’ dreams in this arena, when he showed that there is not even any way to express in PM notation the English statement “n is the Gödel number of a true formula of number theory”. What Tarski’s finding means is that although there is an infinite set of numbers that stand for true statements (using some particular Gödel numbering), and a complementary infinite set of numbers that stand for false statements, there is no way to express that distinction as a number-theoretical one. In other words, the set of all wff numbers is divided into two complementary parts by the true/false dichotomy, but the boundary line is so peculiar and elusive that it is not characterizable in any mathematical fashion at all.

  All of this may seem terribly perverse, but if so, it is a wonderful kind of perversity, in that it reveals the profundity of humanity’s age-old goals in mathematics. Our collective quest for mathematical truth is shown to be a quest for something indescribably subtle and therefore, in a sense, sacred. I’m reminded again that the name “Gödel” contains the word “God” — and who knows what further mysteries are lurking in the two dots on top?

  The Upside-down Perceptions of Evolved Creatures

  As the above excursion has shown, strange loops in mathematical logic have very surprising properties, including what appears to be a kind of upside-down causality. But this is by no means the first time in this book that we have encountered upside-down causality. The notion cropped up in our discussion of the careenium and of human brains. We concluded that evolution tailored human beings to be perceiving entities — entities that filter the world into macroscopic categories. We are consequently fated to describe what goes on about us, including what other people do and what we ourselves do, not in terms of the underlying particle physics (which lies many orders of magnitude removed from our everyday perceptions and our familiar categories), but in terms of such abstract and ill-defined high-level patter
ns as mothers and fathers, friends and lovers, grocery stores and checkout stands, soap operas and beer commercials, crackpots and geniuses, religions and stereotypes, comedies and tragedies, obsessions and phobias, and of course beliefs and desires, hopes and fears, dreads and dreams, ambitions and jealousies, devotions and hatreds, and so many other abstract patterns that are a million metaphorical miles from the microworld of physical causality.

  There is thus a curious upside-downness to our normal human way of perceiving the world: we are built to perceive “big stuff” rather than “small stuff”, even though the domain of the tiny seems to be where the actual motors driving reality reside. The fact that our minds see only the high level while completely ignoring the low level is reminiscent of the possibilities of high-level vision that Gödel revealed to us. He found a way of taking a colossally long PM formula (KG or any cousin) and reading it in a concise, easily comprehensible fashion (“KG has no proof in PM”) instead of reading it as the low-level numerical assertion that a certain gargantuan integer possesses a certain esoteric recursively defined number-theoretical property (non-primness). Whereas the standard low-level reading of a PM string is right there on the surface for anyone to see, it took a genius to imagine that a high-level reading might exist in parallel with it.