# TRANSFINITE NUMBERS

In my novel White Light, I describe a mountain that is higher than infinity.4 This mountain, called Mount On, Consists of alternating cliffs and meadows. The curious thing about it is that even after one has climbed ten cliffs, a thousand cliffs, infinitely many cliffs . . . there are always more cliffs. The climbers of Mount On are able to make some progress because they are able to execute a procedure called a "speed-up." By' using speed-ups they are able, for instance, to zip past the first infinity of cliffs in two hours.

How is this done? The idea is to climb the first cliff in one hour, the next cliff in half an hour, the one after that in a quarter of an hour, and, in general, the nth cliff in 1/ hours. Since 1 + 1/2 + 1/4 + 1/8 + . . . sums to 2, we see that after two hours our climbers have passed infinitely many cliffs. But there are more, many more.

In this section we will climb up through the transfinite numbers, which are usually called ordinal numbers, or just ordinals. Typically, one describes some ordinal a by giving an example of an ordered set M such that if one could count M in the correct order, then one would count up to a. a is then viewed as the abstract order type of M, called for short. The ordinal is gotten from the ordered set M by ignoring the actual appearance of the individual members of M and instead concentrating on the arrangement, or order, of these members.

The transfinite ordinal numbers can be thought of as arising through counting. There are two principles for generating ordinal numbers: I) if you have the ordinal number a, then you can find a next ordinal, called a + 1; II) if you have some definite sequence of increasing ordinals a, then you can find a last ordinal which is greater than all the a's, called lim(a).

We also need a first ordinal to start with, called 0. (Strictly speaking, the second principle for generating ordinals gives us 0, since zero is the first ordinal after the empty sequence.) In any case, once we have zero, the first principle can be repeatedly applied to get the ordinal numbers 0, 1, 2, . . . . Now, to get past the infinite sequence of finite ordinals we use principle II to get lim(n), usually called , pronounced "omega." (Omega is also sometimes called "alef-null.")

Omega is the last letter in the Greek alphabet (they put zeta somewhere in the middle), which may be why Cantor chose to use it as the number after all the finite numbers. The word "omega" is somewhat familiar, as it appears in the Book of Revelations, where God is quoted as saying, "I am the Alpha and the Omega," meaning, "I am the beginning and the end."

Now we have 0, 1, 2,. . . . Using principle I repeatedly we get the sequence 0, 1, 2, . . . , +1, + 2, + 3 . . . . To go further, we use principle II to form lim( + n), which is usually called + or * 2.

You might wonder why lim( + n), + , and * 2 should all be the same. It turns out that there is a definite way to define addition and multiplication of infinite ordinals so that everything works out. let me briefly explain. The ordinal number a + b is obtained by counting out to a and then counting b steps further. The ordinal number a . b is obtained by counting up to a, b times in a row. That is, a * b is obtained by sticking together b copies of a, treating this as an ordered set M, and then abstracting to get the ordinal number= a * b.

As long as one sticks to finite ordinals, these operations are the same as the ordinary' plus and times, and they are commutative. However, once we start working with infinite ordinals, commutativity no longer holds. Thus,

1 + is just the same as , but + 1 is the next number after . Again,

* 2 is two omegas placed next to each other, which gives an ordinal

+ , but 2 * is omega twos placed next to each other, which makes

an ordered set with ordinal number .

Moving on with the ordinals, by using principle I repeatedly, we now have 0, 1, 2, . . ., + 1, + 2, . . . , *2, *2 + 1, * 2 + 2, . . . . It is evident that lim(*2 + n) should be the ordinal * 2 + also known as * 3. Continuing in this vein, we can arrive at * n for each finite n, and using principle II we form lim(*n), which should be Omega copies of omega, that is, * , also known as.

In order to see how to pass from to to and finally on to ), it will be useful to look at the pictures in Figure 41.1 will now describe four sets of points, M1, M2, M3, and M. In each case, the set of points can be thought of as lying between zero and one on the real number line, and each Mi will be such that if we view it as an ordered set and abstract to form the ordinal number Mi, we arrive at . One may wonder how to fit an ordered set with ordinal number in between zero and one on the real line, since the space available seems to be finite. The trick is based on Zeno's paradox: if you start out going from zero to one, but do it by first going halfway, and then going half the remaining distance, and then half the remaining distance, and so on . . . always going just half of what's left . . . then it will take you omega steps to get there. This is basically what the first picture shows.

The second picture is obtained by plugging a copy of the first picture into each of the spaces between points in the first picture. The third picture is obtained by plugging a copy of the second picture into each of the spaces between points in the first picture . . . . at least, this is what we would say if we think of as being *. If, on the other hand, we think of as being * , then we would say that the third picture is obtained by plugging a copy of the first picture into each of the spaces between points in the second picture, thus obtaining copies of (as opposed to copies of .) Both come to the same thing, since although ordinal multiplication is not commutative, it is associative. The fourth picture is obtained by first continuing the process started in the first three pictures endlessly . . . and then putting a copy of each of the pictures together.

I have written next to each picture the real number coordinates of the points involved if we think of the interval as the unit interval on the real line. These set definitions are not particularly important for us, but what is important is to realize that a transfinite arrangement of points can be fitted into a finite space. By using Zenonian squeezing we can sort of see an ordering of type all at once! Transfinite ordinals are not really so inconceivable after all.

It turns out that one can actually fit any countable ordinal into a picture of this nature. (In the next subsection we will look at the uncountable ordinals.) But the illustration of is already something of a mess, and had I not used the arrow symbolism, the picture of would be so lacking in detail as to be quite uninformative. We will look at a different technique for picturing ordinals shortly.

But first let me describe just how far we want to go in this section. One way of characterizing is that it is an ordinal a such that + a = a. This can be seen by thinking of as being + + + + . . . Clearly, putting an " + " in front of this symbol changes nothing. In point of fact, is the first such ordinal.

What about the first ordinal a such that * a = a? If we take to be *** . . . ,we can see that placing an " *" in front of changes nothing. Or, assuming that the familiar laws of exponents hold for ordinals (and they do), we can reason that , since 1 + = . As before, it is possible to prove that is the first ordinal a such that *a = a.

The first ordinal a such that = a is called , pronounced "epsilon zero." Simply by manipulating symbols, we would expect that has the following form:

Evidently, putting such a symbol in the exponent position over an omega does not change anything, since a stack of omegas 1 + high is the same as a stack high.

But we can describe epsilon zero a little better. Suppose that is de- fined to mean "an exponentiated stack of a many b's." is pronounced,

"b tetrated to the a." The name tetration is used since tetra is the Latin root for four, and tetration occurs in fourth place in the logical progression: addition, multiplication, exponentiation, tetration. You don't ordinarily hear much about tetration because it is so powerful an operation that tetrating even very small numbers with each other produces inordinately large numbers. A tetration is worked out below.

Note that we must be careful to associate from the top down, rather than from the bottom up, if we want to get the largest possible numbers.

As further examples, which is just under eight trillion. , which is the number that is written by putting a one and then ten billion zeros (as opposed to, say, a million, which is written by putting a one and then six zeros.) Now, is just ). And , which is kind of hard to get at. One way of visualizing this number is to go back to the picture of , and to imagine replacing each of the dots on the line by the symbol "" to get the product of omegas.

In any case), the point of all this is that is . And the countable ordinals don't stop there. If, for instance), one could make some sense of the following symbol one would have an even larger ordinal.

In trying to think of bigger and bigger ordinals), one sinks into a kind of endless morass. Any procedure you come up with for naming larger ordinals eventually peters out), and the ordinals keep on coming. Finally, your mind snaps, and maybe you get a momentary glimpse of what the

Absolute infinite is all about. Then you try to formalize your glimpse, and you end up with a new system for naming ordinals . . . which eventually peters out. . . . 5

But this is just the beginning. Let us look at a different type of picture of . Suppose that we let PN be the set of all polynomials in x with natural number coefficients. Examples of members of PN would be x, x + 3, +163. Now, suppose that given two polynomials p(x) and q(x) from PN, we define the following order relation: p(x) < bep q(x) if and only if the graph of the polynomial q eventually manages to get above, and stay above, the graph of the polynomial p. (The letters "bep" stand for "by-end-pieces.")

The reason I have brought all this up is that if we take PN with the PN of this ordering is . The correspondence is simplicity itself: the polynomial p(x) represents the transfinite number p() (with the one stipulation that the coefficients of the polynomial must be moved to the right in the translation process that is), 3 + 2x is to correspond to * 3 + * 2).

In Figure 42 1 have illustrated the fact that 0 < bep1 < bep2 < bepx + 1 < bep2x + x , where means x tetrated to the three, ).

Strictly speaking x. If we allow tetration as a standard operation and let PPN be the set of all pseudo-polynomials formed by using natural number coefficients and tetration), as well as exponentiation), then it is not difficult to see that PPN is when PPN is ordered by PPN would be + 2x +78. Note that represents .

The by-end-pieces ordering was first studied by DuBois-Reymond, whose work is interestingly presented in G. H. Hardy's book, Orders of Infinity.6 Felix Hausdorff improved upon Reymond's techniques in his monumental series of papers, "Untersuchen uber Ordnungstypen," in the early 1900s. The term "by-end-pieces ordering" is taken from Kurt Godel, whose research revived interest in this ordering in the 1960s.'

We could really restrict our attention to functions from the natural numbers into the natural numbers. It is amusing to represent ordinal numbers as stacks of such functions, filling in the lines between graph points in the natural way. In order to make the pictures look nice, you leave out parts of the lines to avoid crossings.

I call these pictures "ziggurats" because they look like Babylonian towers or Aztec pyramids. Figure 43 is a ziggurat of height , and Figure 44 shows one of height . In the latter I have not drawn in all the lines, so that it is not so confusing. In every case, the missing line is a line that would hug the line right underneath itself as closely as possible.

### THE ALEFS

The famous mathematician David Hilbert used to illustrate his popular lectures with stories about a hotel with infinitely many rooms.8 This mythical hotel, usually called Hilbert's Hotel, is supposed to have omega rooms: Room 0, Room 1, Room 2,... , Room n, and so on. As in the last section, it is convenient to start counting with 0.

To fix the ideas, I have drawn a picture of Hilbert's Hotel in Figure 45. In order to fit it on the page, I have assumed that each floor is equipped with a science-fictional space condenser, a device that makes each succeeding story two-thirds as high as the one before. The shrinking field also affects the guests. Thus, although the ceilings on Floor 3 are only two or three feet high, the space condenser on that story shrinks the guests to one or two feet), and they are perfectly comfortable. 1 will leave it as an exercise for the reader to check that if the first floor is ten feet high, and each successive floor is two- thirds as high as the one before, then the total height of the hotel's stories is thirty feet.

One of the most paradoxical things about Hilbert's Hotel is that even after it fills up, more and more people can be squeezed in, without making anyone share a room! Say, for instance, that guests have arrived, and every room is occupied with a guest n in each Room n. Now, say that one more guest arrives: Guest . How to fit him in?

Easy! We put Guest in Room 0, which is emptied by moving Guest 0 to Room 1, which is emptied by moving Guest I to Room 2, which is emptied by . . .

Fine! But what if there had been an infinite number of new guests? Even such a procession of + guests could be lodged in Hilbert's Hotel.

We simply put the first guests in the even-numbered rooms, arid the next guests in the odd-numbered rooms.

Now it is in fact possible, by suitable rearrangements, to fit , , or even guests into Hilbert's Hotel. But eventually we do reach a limit to this wonderful hotel's powers of absorption: alef-one, also known as Alef-one is a hard number to describe. One way of putting it is that alef-one is the first ordinal number a such that no possible rearrangement can fit a set of a guests into rooms. Alef-one represents an order of infinity that is essentially greater than in a way that + is not.

To get a better idea of alef-one, let's go back to the idea of people climbing a mountain as high as all the ordinals. How hard will it be for them to get to alef-one?

We will assume that, in the marvelous land where Mount On rises, the climbers can attain any desired finite speed. Then, as we mentioned at the beginning of the "Transfinite Numbers" section, they can scale the infinity of cliffs leading up to in a finite time. If they keep accelerating so that the nth cliff only takes 1/ hours, then they reach after two hours. By repeating this they could reach + in four hours, or, if they did everything four times as fast, they could actually get to + in one hour. Turning to Figure 46, we can see how our climbers could even reach in one hour. The idea is to devote to each of the cliffs the allotted finite interval of time. (Thus, for instance, the stretch between *2 and * 2 + 1 is to be covered during the time interval between 3/4 hour and 13/16 hour.)

Now, the point I want to make is that these climbers could never reach alef-one. There is no way that we can fold together various finite bursts of speed and cover alef-one cliffs in a finite amount of time. The only way to get out to alef-one is by actually going ahead and traveling alef-one miles per hour.

One last picture of alef-one. Go back to Figure 42. In this picture we saw how various ordinals can be represented as sequences of functions ordered according to steepness (the for every g (no matter how steep), there will be an f in S that is steeper, then S must have at least alef-one members.

it is now time to give a formal definition of alef-one. This definition hinges upon the notion of cardinality. Given two ordinals A and B, we say that A has the same cardinality as B if there exists a one-to-one map from A onto B. (When I speak of a map from A onto B, I really mean a map from the set of ordinals less than A onto the set of ordinals less than B.)

In our discussion of Hilbert's Hotel we learned, for instance, that + has the same cardinality as . For there is a way of matching up, in a one-to-one fashion, the members of {O, 1, 2,. . . , + 1, + 2,. . .} with the members of {0,1, 2, . . . }. That is, there is a one-to-one map from + onto . Now, alef-one is defined to be the first ordinal with cardinality greater than . Alef-one is the first ordinal that cannot be mapped one-to-one onto .

In general, we say that the ordinal number A is a cardinal number if arid only if A does not have the same cardinality as any B less than A . All of the natural numbers are cardinals. There is, for instance, no way to find a one-to- one map from three onto two. (Keep in mind that we commonly identify the number N with the set {0, 1,. . . , N - l} of N numbers less than N.)

is, of course, a cardinal number. The infinite number cannot be mapped one-to-one into any of the finite numbers before it. No finite hotel, no matter how large, can sleep infinitely many guests one to a room.

The infinite cardinals are also called alefs. In general, alef-a, or , means the ath infinite cardinal. Thus, alef-null, or , is just , the first (0th) infinite cardinal. It turns out that just as we can always find more ordinals, we can always find more cardinals. After come and so on. After

a while we can even find a number such that = . One way of getting such a is indicated below.

Is this the end? It's never the end, when you're discovering transfinite numbers. After come and so on and on, world without end.

According to the Reflection Principle, it is impossible ever to conceive of an end to the ordinals. We do have a symbol , the big , which we use to stand for the Absolute Infinity that lies beyond all the ordinals. But is inconceivable. The Reflection Principle makes this precise by saying that any description D of that we might come up with will apply to some ordinal a short of .

is called Absolute Infinity because it is not a relative notion. The line of ordinals leading out to contains all the ordinals, all the possible stages of counting. It is because every possible ordinal occurs before that is not really a definite ordinal number. Confusing talk! If you would like to read more about and the transfinite numbers plan to take Excursion I.