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