Gödel, Escher, Bach: An Eternal Golden Braid (13 page)

People enjoy inventing slogans which violate basic arithmetic but which illustrate

"deeper" truths, such as "1 and 1 make 1" (for lovers), or "1 plus 1 plus 1 equals 1" (the Trinity). You can easily pick holes in those slogans, showing why, for instance, using the plus-sign is inappropriate in both cases. But such cases proliferate. Two raindrops running down a windowpane merge; does one plus one make one? A cloud breaks up into two clouds-more evidence for the same? It is not at all easy to draw a sharp line between cases where what is happening could be called "addition", and where some other word is wanted. If you think about the question, you will probably come up with some criterion involving separation of the objects in space, and making sure each one is clearly distinguishable from all the others. But then how could one count ideas? Or the number of gases comprising the atmosphere? Somewhere, if you try to look it up, you can probably find a statement such as, "There are 17 languages in India, and 462 dialects."

There is something strange about precise statements like that, when the concepts

"language" and "dialect" are themselves fuzzy.

Ideal Numbers

Numbers as realities misbehave. However, there is an ancient and innate sense in people that numbers ought not to misbehave. There is something clean and pure in the abstract notion of number, removed from counting beads, dialects, or clouds; and there ought to be a way of talking about numbers without always having the silliness of reality come in and intrude. The hard-edged rules that govern "ideal" numbers constitute arithmetic, and their more advanced consequences constitute number theory. There is only one relevant question to be asked, in making the transition from numbers as practical things to numbers as formal things. Once you have

FIGURE 13. Liberation, by M.C. Escher (lithograph, 1955).

decided to try to capsulize all of number theory in an ideal system, is it really possible to do the job completely? Are numbers so clean and crystalline and regular that their nature can be completely captured in the rules of a formal system? The picture
Liberation
(Fig.

13), one of Escher's most beautiful, is a marvelous contrast between the formal and the informal, with a fascinating transition region. Are numbers really as free as birds? Do they suffer as much from being crystallized into a rule-obeying system? Is there a magical transition region between numbers in reality and numbers on paper?

When I speak of the properties of natural numbers, I don't just mean properties such as the sum of a particular pair of integers. That can be found out by counting, and anybody who has grown up in this century cannot doubt the mechanizability of such processes as counting, adding, multiplying, and so on. I mean the kinds of properties which mathematicians are interested in exploring, questions for which no counting-process is sufficient to provide the answer-not even theoretically sufficient. Let us take a classic example of such a property of natural numbers. The statement is: "There are infinitely many prime numbers." First of all, there is no counting process which will ever be able to confirm, or refute, this assertion. The best we could do would be to count primes for a while and concede that there are "a lot". But no amount of counting alone would ever resolve the question of whether the number of primes is finite or infinite.

There could always be more. The statement-and it is called "Euclid's Theorem" (notice the capital "T")-is quite unobvious. It may seem reasonable, or appealing, but it is not obvious. However, mathematicians since Euclid have always called it true. What is the reason?

Euclid's Proof

The reason is that
reasoning
tells them it is so. Let us follow the reasoning involved. We will look at a variant of Euclid's proof. This proof works by showing that whatever number you pick, there is a prime larger than it. Pick a number-N. Multiply all the positive integers starting with 1 and ending with N; in other words, form the factorial of N, written "N!". What you get is divisible by every number up to N. When you add 1 to N!, the result

can't be a multiple of 2 (because it leaves 1 over, when you divide by 2);

can't be a multiple of 3 (because it leaves I over, when you divide by 3);

can't be a multiple of 4 (because it leaves 1 over, when you divide by 4);

.

.

.

can't be a multiple of
N
(because it leaves 1 over, when you divide by
N
);

In other words,
N
! + 1, if it is divisible at all (other than by 1 and itself only is divisible by numbers greater than
N
. So either it is itself prime, or prime divisors are greater than
N.
But in either case we've shown the must exist a prime above
N
. The process holds no matter what number is. Whatever N is, there is a prime greater than
N
.

And thus ends the demonstration of the infinitude of the primes.

This last step, incidentally, is called
generalization
, and we will meet again later in a more formal context. It is where we phrase an argument terms of a single number (
N
), and then point out that
N
was unspecified and therefore the argument is a general one.

Euclid's proof is typical of what constitutes "real mathematics". It simple, compelling, and beautiful. It illustrates that by taking several rash short steps one can get a long way from one's starting point. In our case, t starting points are basic ideas about multiplication and division and forth. The short steps are the steps of reasoning. And though eve individual step of the reasoning seems obvious, the end result is not obvious.

We can never check directly whether the statement is true or not; } we believe it, because we believe in reasoning. If you accept reasoning there seems to be no escape route; once you agree to hear Euclid out, you’ll have to agree with his conclusion. That's most fortunate-because it mea that mathematicians will always agree on what statements to label "true and what statements to label "false".

This proof exemplifies an orderly thought process. Each statement related to previous ones in an irresistible way. This is why it is called "proof' rather than just "good evidence". In mathematics the goal always to give an ironclad proof for some unobvious statement. The very fact of the steps being linked together in an ironclad way suggests ti there may be a
patterned structure
binding these statements together. TI structure can best be exposed by finding a new vocabulary-a stylized vocabulary, consisting of symbols-suitable only for expressing statements about numbers. Then we can look at the proof as it exists in its translated version. It will be a set of statements which are related, line by line, in some detectable way. But the statements, since they're represented by means a small and stylized set of symbols, take on the aspect of patterns. In other words, though when read aloud, they seem to be statements about numb and their properties, still when looked at on paper, they seem to be abstract patterns-and the line-by-line structure of the proof may start to look like slow transformation of patterns according to some few typographical rules.

Getting Around Infinity

Although Euclid's proof is a proof that
all
numbers have a certain property it avoids treating each of the infinitely many cases separately. It gets around it by using phrases like "whatever
N
is", or "no matter what number
N
is". We could also phrase-the proof over again, so that it uses the phrase "all
N
". By knowing the appropriate context and correct ways of using such phrases, we never have to deal with infinitely many statements. We deal with just two or three concepts, such as the word "all"-which, though themselves finite, embody an infinitude; and by using them, we sidestep the apparent problem that there are an infinite number of facts we want to prove.

We use the word "all" in a few ways which are defined by the thought processes of reasoning. That is, there are
rules
which our usage of "all" obeys. We may be unconscious of them, and tend to claim we operate on the basis of the
meaning
of the word; but that, after all, is only a circumlocution for saying that we are guided by rules which we never make explicit. We have used words all our lives in certain patterns, and instead of calling the patterns "rules", we attribute the courses of our thought processes to the "meanings" of words. That discovery was a crucial recognition in the long path towards the formalization of number theory.

If we were to delve into Euclid's proof more and more carefully, we would see that it is composed of many, many small-almost infinitesimal steps. If all those steps were written out line after line, the proof would appear incredibly complicated. To our minds it is clearest when several steps are telescoped together, to form one single sentence. If we tried to look at the proof in slow motion, we would begin to discern individual frames. In other words, the dissection can go only so far, and then we hit the "atomic" nature of reasoning processes. A proof can be broken down into a series of tiny but discontinuous jumps which seem to flow smoothly when perceived from a higher vantage point. In Chapter VIII, I will show one way of breaking the proof into atomic units, and you will see how incredibly many steps are involved. Perhaps it should not surprise you, though.

The operations in Euclid's brain when he invented the proof must have involved millions of neurons (nerve cells), many of which fired several hundred times in a single second.

The mere utterance of a sentence involves hundreds of thousands of neurons. If Euclid's thoughts were that complicated, it makes sense for his proof to contain a huge number of steps! (There may be little direct connection between the neural actions in his brain, and a proof in our formal system, but the complexities of the two are comparable. It is as if nature wants the complexity of the proof of the infinitude of primes to be conserved, even when the systems involved are very different from each other.)

In Chapters to come, we will lay out a formal system that (1) includes a stylized vocabulary in which all statements about natural numbers can be expressed, and (2) has rules corresponding to all the types of reasoning which seem necessary. A very important question will be whether the rules for symbol manipulation which we have then formulated are really of equal power (as far as number theory is concerned) to our usual mental reasoning abilities-or, more generally, whether it is theoretically possible to attain the level of our thinking abilities, by using some formal system.

Sonata

for Unaccompanied Achilles

The telephone rings; Achilles picks it up.

Achilles: Hello, this is Achilles.

Achilles: Oh, hello, Mr. T. How are you?

Achilles: A torticollis? Oh, I'm sorry to hear it. Do you have any idea what caused it?

Achilles: How long did you hold it in that position?

Achilles: Well, no wonder it's stiff, then. What on earth induced you keep your neck twisted that way for so long?

Achilles: Wondrous many of them, eh? What kinds, for example? Achilles: What do you mean, "phantasmagorical beasts"?

FIGURE 14. Mosaic II, by M. C. Escher (lithograph, 1957).

Achilles: Wasn't it terrifying to see so many of them at the same time? Achilles: A guitar!? Of all things to be in the midst of all those weird creatures. Say, don't you play the guitar?