When I was sixteen, I had the unusual experience of teaching symbolic logic at Stanford Elementary School (my own elementary-school alma mater), using a brand-new text by the philosopher and educator Patrick Suppes, who happened to live down the street from our family, and whose classic Introduction to Logic had been one of my most reliable guides. Suppes was conducting an experiment to see if patterns of strict logical inference could be inculcated in children in the same way as arithmetic could, and the school’s principal, who knew me well from my years there, one day bumped into me in the school’s rotunda, and asked me if I would like to teach the sixth-grade class (which included my sister Laura) symbolic logic three times a week for a whole year. I fairly jumped at the chance, and all year long I thoroughly enjoyed it, even if a few of the kids now and then gave me a hard time (rubber bands in the eye, etc.). I taught my class the use of many rules of inference, including the mellifluous modus tollendo tollens and the impressive-sounding “hypothetical syllogism”, and all the while I was honing my skills not only as a novice logician but also as a teacher.
What drove all this — my core inner passion — was a burning desire to see unveiled the secrets of human mentation, to come to understand how it could be that trillions of silent, synchronized scintillations taking place every second inside a human skull enable a person to think, to perceive, to remember, to imagine, to create, and to feel. At more or less the same time, I was reading books on the brain, studying several foreign languages, exploring exotic writing systems from various countries, inventing ways to get a computer to generate grammatically complicated and quasi-coherent sentences in English and in other languages, and taking a marvelously stimulating psychology course. All these diverse paths were focused on the dense nebula of questions about the relationship between mind and mechanism, between mentality and mechanicity.
Intricately woven together, then, in my adolescent mind were the study of pattern (mathematics) and the study of paradoxes (metamathematics). I was somehow convinced that all the mysterious secrets with which I was obsessed would become crystal-clear to me once I had deeply mastered these two intertwined disciplines. Although over the course of the next couple of decades I lost essentially all of my faith in the notion that these disciplines contained (even implicitly) the answers to all these questions, one thing I never lost was my intuitive hunch that around the core of the eternal riddle “What am I?”, there swirled the ethereal vortex of Gödel’s elaborately constructed loop.
It is for that reason that in this book, although I am being driven principally by questions about consciousness and self, I will have to devote some pages to the background needed for a (very rough) understanding of Gödel’s ideas — and in particular, this means number theory and logic. There won’t be heavy doses of either one, to be sure, but I do have to paint at least a coarse-grained picture of what these fields are basically about; otherwise, we won’t have any way to proceed. So please fasten your seat belt, dear reader. We’re going to be experiencing a bit of weather for the next two chapters.
Post Scriptum
After completing this chapter to my satisfaction, I recalled that I owned two books about “interesting numbers” — The Penguin Dictionary of Curious and Interesting Numbers by David Wells, an author on mathematics whom I greatly admire, and Les nombres remarquables by François Le Lionnais, one of the two founders of the famous French literary movement Oulipo. I dimly recalled that both of these books listed their “interesting numbers” in order of size, so I decided to check them out to see which was the lowest integer that each of them left out.
As I suspected, both authors made rather heroic efforts to include all the integers that exist, but inevitably, human knowledge being finite and human beings being mortal, each volume sooner or later started having gaps. Wells’ first gap appeared at 43, while Le Lionnais held out a little bit longer, until 49. I personally was not too surprised by 43, but I found 49 surprising; after all, it’s a square, which suggests at least a speck of interest. On the other hand, I admit that squareness gets a bit boring after you’ve already run into it several times, so I could partially understand why that property alone did not suffice to qualify 49 for inclusion in Le Lionnais’s final list. Wells lists several intriguing properties of 49 (but not the fact that it’s a square), and conversely, Le Lionnais points out some very surprising properties of 43.
So then I decided to find the lowest integer that both books considered to be utterly devoid of interest, and this turned out to be 62. For what it’s worth, that will be my age when this book appears in print. Could it be that 62 is interesting, after all?
CHAPTER 9
Pattern and Provability
Principia Mathematica and its Theorems
IN THE early twentieth century, Bertrand Russell, spurred by the maxim “Find and study paradoxes; design and build great ramparts to keep them out!” (my words, not his), resolved that in Principia Mathematica, his new barricaded fortress of mathematical reasoning, no set could ever contain itself, and no sentence could ever turn around and talk about itself. These parallel bans were intended to save Principia Mathematica from the trap that more naïve theories had fallen into. But something truly strange turned up when Kurt Gödel looked closely at what I will call PM — that is, the formal system used in Principia Mathematica for reasoning about sets (and about numbers, but they came later, as they were defined in terms of sets).
Let me be a little more explicit about this distinction between Principia Mathematica and PM. The former is a set of three hefty tomes, whereas PM is a set of precise symbol-manipulation rules laid out and explored in depth in those tomes, using a rather arcane notation (see the end of this chapter). The distinction is analogous to that between Isaac Newton’s massive tome entitled Principia and the laws of mechanics that he set forth therein.
Although it took many chapters of theorems and derivations before the rather lowly fact that one plus one equals two (written in PM notation as “s0 + s0 = ss0”, where the letter “s” stands for the concept “successor of ”) was rigorously demonstrated using the strict symbol-shunting rules of PM, Gödel nonetheless realized that PM, though terribly cumbersome, had enormous power to talk about whole numbers — in fact, to talk about arbitrarily subtle properties of whole numbers. (By the way, that little phrase “arbitrarily subtle properties” already gives the game away, though the hint is so veiled that almost no one is aware of how much the words imply. It took Gödel to fully see it.)
For instance, as soon as enough set-theoretical machinery had been introduced in Principia Mathematica to allow basic arithmetical notions like addition and multiplication to enter the picture, it became easy to define, within the PM formalism, more interesting notions such as “square” (i.e., the square of a whole number), “nonsquare”, “prime”, and “composite”.
There could thus be, at least in theory, a volume of Principia Mathematica devoted entirely to exploring the question of which integers are, and which are not, the sum of two squares. For instance, 41 is the sum of 16 and 25, and there are infinitely many other integers that can be made by summing two squares. Call them members of Class A. On the other hand, 43 is not the sum of any pair of squares, and likewise, there are infinitely many other integers that cannot be made by summing two squares. Call them members of Class B. (Which class is 109 in? What about 133?) Fully fathoming this elegant dichotomy of the set of all integers, though a most subtle task, had been accomplished by number theorists long before Gödel’s birth.
Analogously, one could imagine another volume of Principia Mathematica devoted entirely to exploring the question of which integers are, and which are not, the sum of two primes. For instance, 24 is the sum of 5 and 19, whereas 23 is not the sum of any pair of primes. Once again, we can call these two classes of integers “Class C” and “Class D”, respectively. Each class has infinitely many members. Fully fathoming this elegant dichotomy of the set of all integers represents a very deep and, as of today, still unso
lved challenge for number theorists, though much progress has been made in the two-plus centuries since the problem was first posed.
Mixing Two Unlikely Ideas: Primes and Squares
Before we look into Gödel’s unexpected twist-based insight into PM, I need to comment first on the profound joy in discovering patterns, and next on the profound joy in understanding what lies behind patterns. It is mathematicians’ relentless search for why that in the end defines the nature of their discipline. One of my favorite facts in number theory will, I hope, allow me to illustrate this in a pleasing fashion.
Let us ask ourselves a simple enough question concerning prime numbers: Which primes are sums of two squares (41, for example), and which primes are not (43, for example)? In other words, let’s go back to Classes A and B, both of which are infinite, and ask which prime numbers lie in each of them. Is it possible that nearly all prime numbers are in one of these classes, and just a few in the other? Or is it about fifty–fifty? Are there infinitely many primes in each class? Given an arbitrary prime number p, is there a quick and simple test to determine which class p belongs to (without trying out all possible additions of two squares smaller than p)? Is there any kind of predictable pattern concerning how primes are distributed in these two classes, or is it just a jumbly chaos?
To some readers, these may seem like peculiar or even unnatural questions to tackle, but mathematicians are constitutionally very curious people, and it happens that they are often deeply attracted by the idea of exploring interactions between concepts that do not, a priori, seem related at all (such as the primes and the squares). What often happens is that some kind of unexpected yet intimate connection turns up — some kind of crazy hidden regularity that feels magical, the discovery or the revelation of which may even send mystical frissons up and down one’s spine. I, for one, shamelessly admit to being highly susceptible to such spine-tingling mixtures of awe, beauty, mystery, and surprise.
To get a feel for this kind of thing, let us take the list of all the primes up to 100 — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 — a rather jumbly, chaotic list, by the way — and redisplay it, highlighting those primes that are sums of two squares (that is, Class A primes), and leaving untouched those that are not (Class B primes). Here is what we get:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ,…
Do you see anything interesting going on here? Well, for one thing, isn’t it already quite a surprise that it seems to be a fairly even competition? Why should that be the case? Why shouldn’t either Class A or Class B be dominant? Will either the Class A primes or the Class B primes take over after a while, or will their roughly even balance continue forever? As we go out further and further towards infinity, will the balance tend closer and closer to being exactly fifty–fifty? If so, why would such an amazing, delicate balance hold? To me, there is something enormously alluring here, and so I encourage you to look at this display for a little while — a few minutes, say — and try to find any patterns in it, before going on.
Pattern-hunting
All right, reader, here we are, back together again, hopefully after a bit of pattern-searching on your part. Most likely you noticed that our act of highlighting seems, not by intention but by chance (or is it chance?), to have broken the list into singletons and pairs. A hidden connection revealed?
Let’s look into this some more. The boldface pairs are 13–17, 37–41, and 89–97, while the non-boldface pairs are 7–11, 19–23, 43–47, 67–71, and 79–83. Suppose, then, that we replace each pair by the letter “P” and each singleton by the letter “S”, retaining the highlighting that distinguishes Class A from Class B. We then get the following sequence of letters:
S, S, S, P, P, P, S, S, P, P, S, S, S, P, S, P, P, . . .
Is there some kind of pattern here, or is there none? What do you think? If we pull out just the Class-A letters, we get this: SSPSPSSSP; and if we pull out just the Class-B letters, we get this: SPPSPSPP. If there is any kind of periodicity or subtler type of rhythmicity here, it’s certainly elusive. No simple predictable pattern jumps out either in boldface or in non-boldface, nor did any jump out when they were mixed together. We have picked up a hint of a quite even balance between the two classes, yet we lack any hints as to why that might be. This is provocative but frustrating.
People who Pursue Patterns with Perseverance
At this juncture, I feel compelled to point out a distinction not between two classes of numbers, but between two classes of people. There are those who will immediately be drawn to the idea of pattern-seeking, and there are those who will find it of no appeal, perhaps even distasteful. The former are, in essence, those who are mathematically inclined, and the latter are those who are not. Mathematicians are people who at their deepest core are drawn on — indeed, are easily seduced — by the urge to find patterns where initially there would seem to be none. The passionate quest after order in an apparent disorder is what lights their fires and fires their souls. I hope you are among this class of people, dear reader, but even if you are not, please do bear with me for a moment.
It may seem that we have already divined a pattern of sorts — namely, that we will forever encounter just singletons and pairs. Even if we can’t quite say how the S’s and P’s will be interspersed, it appears at least that the imposition of the curious dichotomy “sums-of-two-squares vs. not-sums-of-two-squares” onto the sequence of the prime numbers breaks it up into singletons and pairs, which is already quite a fantastic discovery! Who would have guessed?
Unfortunately, I must now confess that I have misled you. If we simply throw the very next prime, which is 101, into our list, it sabotages the seeming order we’ve found. After all, the prime number 101, being the sum of the two squares 1 and 100, and thus belonging to Class A, has to be written in boldface, and so our alleged boldface pair 89–97 turns out to be a boldface triplet instead. And thus our hopeful notion of a sequence of just S’s and P’s goes down the drain.
What does a pattern-seeker do at this point — give up? Of course not! After a setback, a flexible pattern-seeker merely regroups. Indeed, taking our cue from the word just given, let us try regrouping our sequence of primes in a different fashion. Suppose we segregate the two classes, displaying them on separate lines. This will give us the following:
Yes square + square: 2, 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101,…
No square + square: 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83,…
Do you see anything yet? If not, let me give you a hint. What if you simply take the differences between adjacent numbers in each line? Try it yourself — or else, if you’re very lazy, then just read on.
In the upper line, you will get 3, 8, 4, 12, 8, 4, 12, 8, 12, 16, 8, 4, whereas in the lower line you will get 4, 4, 8, 4, 8, 12, 4, 12, 8, 4, 8, 4. There is something that surely should jump out at even the most indifferent reader at this point: not only is there a preponderance of just a few integers (4, 8, and 12), but moreover, all these integers are multiples of 4. This seems too much to be merely coincidental.
And the only larger number in these two lists — 16 — is also a multiple of 4. Will this new pattern — multiples of 4 exclusively — hold up forever? (Of course, there is that party-pooper of a ‘3’ at the very outset, but we can chalk it up to the fact that 2 is the only even prime. No big deal.)
Where There’s Pattern, There’s Reason
The key thought in the preceding few lines is the article of faith that this pattern cannot merely be a coincidence. A mathematician who finds a pattern of this sort will instinctively ask, “Why? What is the reason behind this order?” Not only will all mathematicians wonder what the reason is, but even more importantly, they will all implicitly believe that whether or not anyone ever finds the reason, there must be a reason for it. Nothing happens “by accident” in the world of mathematics. The existence of a perfect pattern, a reg
ularity that goes on forever, reveals — just as smoke reveals a fire — that something is going on behind the scenes. Mathematicians consider it a sacred goal to seek that thing, uncover it, and bring it out into the open.
This activity is called, as you well know, “finding a proof ”, or stated otherwise, turning a conjecture into a theorem. The late great eccentric Hungarian mathematician Paul Erdös once made the droll remark that “a mathematician is a device for turning coffee into theorems”, and although there is surely truth in his witticism, it would be more accurate to say that mathematicians are devices for finding conjectures and turning them into theorems.
What underlies the mathematical mindset is an unshakable belief that whenever some mathematical statement X is true, then X has a proof, and vice versa. Indeed, to the mathematical mind, “having a proof ” is no more and no less than what “being true” means! Symmetrically, “being false” means “having no proof ”. One can find hints of a perfect, infinite pattern by doing numerical explorations, as we did above, but how can one know for sure that a suspected regularity will continue forever, without end? How can one know, for instance, that there are infinitely many prime numbers? How do we know there will not, at some point, be a last one — the Great Last Prime P?
I Am a Strange Loop Page 17
