I Am a Strange Loop (27 page)

And yet for a mathematician, this flash of joy is only the beginning of the story. It is like a murder mystery: we have found out someone is dead, but whodunnit? There always has to be an explanation. It may not be easy to find or easy to understand, but it has to exist.

Here, we know (or at least we strongly suspect) that there is a beautiful infinite pattern, but
for what reason
? The bedrock assumption is that there
is
a reason here — that our pattern, far from being an “infinite coincidence”, comes from one single compelling, underlying reason; that behind all these infinitely many “independent” facts lies just one phenomenon.

As it happens, there is actually much more to the pattern we have glimpsed. Not only are primes of the form 4
n
+ 3 never the sum of two squares (proving this is easy), but also it turns out that every prime number of the form 4
n
+ 1 has
one and only one way
of being the sum of two squares. Take 101, for example. Not only does 101 equal 100 + 1, but there is no other sum of two squares that yields 101. Finally, it turns out that in the limit, as one goes further and further out, the ratio of the number of Class A primes to the number of Class B primes grows ever closer to 1. This means that the delicate balance that we observed in the primes below 100 and conjectured would continue
ad infinitum
is rigorously provable.

Although I will not go further into this particular case study, I will state that many textbooks of number theory prove this theorem (it is far from trivial), thus supplementing a pattern with a proof. As I said earlier, X is true
because
X has a proof, and conversely, X is true
and so
X has a proof.

The Long Search for Proofs, and for their Nature

I mentioned above that the question “Which numbers are sums of two primes?”, posed almost 300 years ago, has never been fully solved. Mathematicians are dogged searchers, however, and their search for a proof may go on for centuries, even millennia. They are not discouraged by eons of failure to find a proof of a mathematical pattern that, from numerical trends, seems likely to go on and on forever. Indeed, extensive empirical confirmation of a mathematical conjecture, which would satisfy most people, only makes mathematicians more ardent and more frustrated. They want a proof as good as Euclid’s, not just lots of spot checks! And they are driven by their belief that a proof
has
to exist — in other words, that
if no proof existed,
then the pattern in question would have to be
false.

This, then, constitutes the flip side of the Mathematician’s Credo:

X is false
because
there is no proof of X;
X is false
and so
there is no proof of X.

In a word, just as provability and truth are the same thing for a mathematician, so are nonprovability and falsity. They are synonymous.

During the centuries following the Renaissance, mathematics branched out into many subdisciplines, and proofs of many sorts were found in all the different branches. Once in a while, however, results that were clearly absurd seemed to have been rigorously proven, yet no one could pinpoint where things had gone awry. As stranger and stranger results turned up, the uncertainty about the nature of proofs became increasingly disquieting, until finally, in the middle of the nineteenth century, a powerful movement arose whose goal was to specify just what reasoning really was, and to bond it forever with mathematics, fusing the two into one.

Many philosophers and mathematicians contributed to this noble goal, and around the turn of the twentieth century it appeared that the goal was coming into sight. Mathematical reasoning seemed to have been precisely characterized as the repeated use of certain basic rules of logic, dubbed
rules of inference,
such as
modus ponens
: If you have proven a result X and you have also proven X ⇒ Y (where the arrow represents the concept of implication, so that the line means “If X is true, then Y is also true”), then you can toss Y into the bin of proven results. There were a few other fundamental rules of inference, but it was agreed that not very many were needed. About a decade into the twentieth century, Bertrand Russell and Alfred North Whitehead codified these rules in a uniform if rather prickly notation (see facing page), thus apparently allowing all the different branches of mathematics to be folded in with logic, making a seamless, perfect unity.

Thanks to Russell and Whitehead’s grand work,
Principia Mathematica,
people no longer needed to fear falling into hidden crevasses of false reasoning. Theorems were now understood as simply being the bottom lines of sequences of symbol-manipulations whose top lines were either axioms or earlier theorems. Mathematical truth was all coming together so elegantly. And as this Holy Grail was emerging into clear view, a young boy was growing up in the town of Brünn, Austro-Hungary.

CHAPTER 10

Gödel’s Quintessential Strange Loop

Gödel Encounters Fibonacci

B
Y HIS early twenties, the boy from Brünn was already a superb mathematician and, like all mathematicians, he knew whole numbers come in limitless varieties. Aside from squares, cubes, primes, powers of ten, sums of two squares, and all the other usual suspects, he was familiar with many other types of integers. Most crucially for his future, young Kurt knew, thanks to Leonardo di Pisa (more often known as “Fibonacci”), that one could define classes of integers
recursively.

In the 1300’s, Fibonacci had concocted and explored what are now known as the “Fibonacci numbers”:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, . . .

In this rapidly growing infinite sequence, whose members I will henceforth refer to as the
F
numbers, each new element is created by summing the two previous ones (except for the first pair, 1 and 2, which we simply declare by fiat to be
F
numbers).

This almost-but-not-quite-circular fashion of defining a sequence of numbers in terms of itself is called a “recursive definition”. This means there is some kind of precise calculational rule for making new elements out of previous ones. The rule might involve adding, multiplying, dividing, whatever — as long as it’s well-defined. The opening gambit of a recursive sequence (in this case, the numbers 1 and 2) can be thought of as a
packet of seeds
from which a gigantic plant — all of its branches and leaves, infinite in number — grows in a predetermined manner, based on the fixed rule.

The Caspian Gemstones: An Allegory

Leonardo di Pisa’s sequence is brimming with amazing patterns, but unfortunately going into that would throw us far off course. Still, I cannot resist mentioning that 144 jumps out in this list of the first few
F
numbers because it is a salient perfect square. Aside from 8, which is a cube, and 1, which is a rather degenerate case, no other perfect square, cube, or any other exact power appears in the first few hundred terms of the
F
sequence.

Several decades ago, people started wondering if the presence of 8 and 144 in the
F
sequence was due to a
reason,
or if it was just a “random accident”. Therefore, as computational tools started becoming more and more powerful, they undertook searches. Curiously enough, even with the advent of supercomputers, allowing millions and even billions of
F
numbers to be churned out, no one ever came across any other perfect powers in Fibonacci’s sequence. The chance of a power turning up very soon in the
F
sequence was looking slim, but why would a
perfect
mutual avoidance occur? What do
n
th powers for arbitrary
n
have to do with adding up pairs of numbers in Fibonacci’s peculiar recursive fashion? Couldn’t 8 and 144 just be little random glitches? Why couldn’t other little glitches take place?

To cast allegorical light on this, imagine someone chanced one day to fish up a giant diamond, a magnificent ruby, and a tiny pearl at the bottom of the great green Caspian Sea in central Asia, and other seekers of fortune, spurred on by these stunning finds, then started madly dredging the bottom of the world’s largest lake to seek more diamonds, rubies, pearls, emeralds, topazes, etc., but none was found, no matter how much dredging was done. One would naturally wonder if more gems might be hidden down there, but how could one ever know? (Caveat: my allegory is slightly flawed, because we can imagine, at least in principle, a richly financed scientific team someday dredging the lake’s bottom completely, since, though huge, it is finite. For my analogy to be “perfect”, we would have to conceive of the Caspian Sea as infinite. Just stretch your imagination a bit, reader!)

Now the twist. Suppose some mathematically-minded geologist set out to
prove
that the two exquisite Caspian gems, plus the tiny round pearl, were
sui generis
— in other words, that there was a precise
reason
that no other gemstone or pearl of any type or size would ever again, or
could
ever again, be found in the Caspian Sea
.
Does seeking such a proof make any sense? How could there be a watertight scientific
reason
absolutely forbidding any gems — except for one pearl, one ruby, and one diamond — from ever being found on the floor of the Caspian Sea? It sounds absurd.

This is typical of how we think about the physical world — we think of it as being filled with contingent events, facts that could be otherwise, situations that have no fundamental reason for their being as they are. But let me remind you that mathematicians see their pristine, abstract world as the antithesis to the random, accident-filled physical world we all inhabit. Things that happen in the mathematical world strike mathematicians as happening, without any exceptions, for statable, understandable
reasons.