Alephs And Supertasks


Have no parts or joints. How then can they combine To form a line?

Every finite set of n elements has 2" subsets if one includes the original set and the null, or empty, set. For example, a set of three elements, ABC, has 23 = 8 subsets: ABC, AB, BC, AC, A, B, C, and the null set. As the philosopher Charles Sanders Peirce once observed (Collected Papers 4. 181), the null set "has obvious logical peculiarities." You can't make any false statement about its members because it has no members. Put another way, if you say anything logically contradictory about its members, you state a truth, because the solution set for the contradictory statement is the null set. Put colloquially, you are saying something true about nothing.

In modern set theory it is convenient to think of the null set as an "existing set" even though it has no members. It can also be said to have 2" subsets because 2° = 1, and the null set has one subset, namely itself. And it is a subset of every set. If set A is included in set B, it means that every member of set A is a member of set B. Therefore, if the null set is to be treated as a legitimate set, all its members (namely none) must be in set B. To prove it by contradiction, assume the null set is not included in set B. Then there must be at least one member of the null set that is not a member of B, but this is impossible because the null set has no members.

T'tie n elements of any finite set obviously cannot be put into orLe-to-one correspondence with its subsets because there are always more than n subsets. Is this also true of infinite sets? The answer is yes, and the general proof is one of the most beautiful in all set theory.

It is an indirect proof, a reductio ad absurdum. Assume that all elements of N, a set with an infinity of members, are matched one-to-one with all of ATs subsets. Each matching must meet one of two conditions:

[1) An element is paired with a subset that includes that element. Let us call all such elements blue.

<(2) An element is paired with a subset that does not include that element. We call all such elements red.

The red elements form a subset of our initial set N. Can this subset be matched to a blue element? No, because every blue element is in its matching subset, therefore the red subset would have to include a blue element. Can the red subset be paired with a red element? No, because the red element would then be included in its subset and would therefore be blue. Since the red subset cannot be matched to either a red or blue elerrnent of N, we have constructed a subset of N that is not paired with any element of N. No set, even if infinite, can be put into one-to-one correspondence with its subsets. If n is a transfinite number, then 2"—by definition it is the number of subsets of n—must be a higher order of infinity than n.

Georg Cantor, the founder of set theory, used the term aleph-null for the lowest transfinite number. It is the cardinal number of the set of all integers, and for that reason is often called a "countable infinity." Any set that can be matched one-to-one with the counting numbers, such as the set of integral fractions, is said to be a countable or aleph-null set. Cantor showed that when 2 is raised to the power of aleph-null—giving the number of subsets of the integers—the result is equal to the cardinal number of the set of all real numbers (rational or irrational), called the "power of the continuum," or c. It is the cardinal number of all points on a line. The line may be a segment of any finite length, a ray with a beginning but no end, or a line going to infinity in both directions. Figure 18 shows three intuitively obvious geometrical proofs that all three kinds of line have the same number of points. The slant lines projected from point P indicate how all points on the line segment AB can be put into one-to-one correspondence with all points on the longer segment, on a ray, and on an endless line.

The red-blue proof outlined above (Cantor published it in 1890) of course generates an infinite hierarchy of transfinite p p a a p b p p a a p b

Number of points on a line segment AB is the same as on a longer line segment (left), a ray (center) and a line (right)

numbers. The ladder starts with the set of counting numbers, aleph-null, next comes c, then all the subsets of c, then all the subsets of all the subsets of c, and so on. The ladder can also be expressed like this:

Cantor called c "aleph-one" because he believed that no transfinite number existed between aleph-null and c. And he called the next number aleph-two, the next aleph-three, and so on. For many years he tried unsuccessfully to prove that c was the next higher transfinite number after aleph-null, a conjecture that came to be called the "continuum hypothesis." We rtow know, thanks to proofs by Kurt Godel and Paul Cohen, that the conjecture is undecidable within standard set theory, ever! when strengthened by the axiom of choice. We can assume without contradiction that Cantor's alephs catch all transfinite numbers, or we can assume, also without contradiction, a non-Cantorian set theory in which there is an infinity of transfinite numbers between any two adjacent entries in Cantor's ladder. (See Chapter 3 of my Mathematical Carnival for a brief, informal account of this.)

Cantor also tried to prove that the number of points on a square is the next higher transfinite cardinal after c. In 1877 he astounded himself by finding an ingenious way to match all the points of a square to all the points of a line segment. Imagine a square one mile on a side, and a line segment one inch long [see Figure 19]. On the line segment every point from 0 to 1 is labeled with an infinite decimal fraction: The point corresponding to the fractional part of pi is .14159 ... , the point corresponding to 1/3 is .33333 . . . and so on. Every point is represented by a unique string of aleph-null digits, and every possible aleph-null string of digits represents a unique point on the line segment. (A slight difficulty arises from the fact that a



Points in square mile and on line segment fraction such, as .5000 ... is the same as .4999 . . . , but it is easily overcome by dodges we need not go into here.)

Now consider the square mile. Using a Cartesian coordinate system, erery point on the square has unique x and y coordinates, each of which can be represented by an endless decimal fraction. The illustration shows a point whose x coordinate is the fractional part of pi and whose y coordinate is the fractional part of the square root of 3, or .73205. . . . Starting with the x coordinate, alternate the digits of the two numbers: .1743125095. . . . The result is an endless decimal labeling a unique point on the line segment. Clearly this can be done with every point on the square. It is equally obvious that the mapping procedure can be reversed: we can select any point on the line segment and, by taking alternate digits of its infinite decimal, can split it into two endless decimals that as coordinates label a unique point on the square. (Here we must recognize and overcome the subtle fact that, for example, the following three distinct points on the segment—.449999 . . . , .459090 . . . , and .540909 . . .—all map the same point [Vn, V2] in the square.) In this way the points of any square can be put into one-to-one correspondence with the points on any line segment; therefore the two sets are equivalent and each has the cardinal number c.

The proof extends easily to a cube (by interlacing three coordinates), or to a hypercube of n dimensions (by interlacing n coordinates). Other proofs show that c also numbers the points in an infinite space of any finite number of dimensions, even an infinite space of aleph-null dimensions.

Cantor hoped that his transfinite numbers would distinguish the different orders of space but, as we have seen, he himself proved that this was not the case. Mathematicians later showed that it is the topological way the points of space go together that distinguishes one space from another. The matchings in the previous paragraphs are not continuous; that is, points close together on, for instance, the line are not necessarily close together on the square, and vice versa. Put another way, you cannot continuously deform a line to make it a square, or a square to make it a cube, or a cube to make a hypercube, and so on.

Is there a set in mathematics that corresponds to 2C? Of course we know it is the number of all subsets of the real numbers, but does it apply to any familiar set in mathematics? Yes, it is the set of all real functions of x, even the set of all real one-valued functions. This is the same as the number of all possible permutations of the points on a line. Geometrically it is all the curves (including discontinuous ones) that can be drawn on a plane or even a small finite portion of a plane the size, say, of a postage stamp. As for 2 to the power of 2C, no one has yet found a set, aside from the subsets of 2C, equal to it. Only aleph-null, c, and 2C seem to have an application outside the higher reaches of set theory. As George Gamow once said, "we find ourselves here in a position exactly opposite to that of . . . the Hottentot who had many sons but could not count beyond three." There is an endless ladder of transfinite numbers, but most mathematicians have only three "sons" to count with them. This has not prevented philosophers from trying to find metaphysical interpretations for the transfinite numbers. Cantor himself, a deeply religious man, wrote at length on such matters. In the United States, Josiah Royce was the philosopher who made the most extensive use of Cantor's alephs, particularly in his work The World and the Individual.

The fact that there is no highest or final integer is involved in a variety of bewildering new paradoxes. Known as super-tasks, they have been much debated by philosophers of science since they were first suggested by the mathematician Hermann Weyl. For instance, imagine a lamp (called the Thomson lamp after James F. Thomson, who first wrote about it) that is turned off and on by a push-button switch. Starting at zero time, the lamp is on for 1/2 minute, then it is off for 1/4 minute, then on for 1/8 minute and so on. Since the sum of this halving series, 1/2 + 1/4 + 1/8 + . . . , is 1, at the end of one minute the switch will have been moved aleph-null times. Will the lamp be on or off?

Everyone agrees that a Thomson lamp cannot be constructed. Is such a lamp logically conceivable or is it nonsense to discuss it in the abstract? One of Zeno's celebrated paradoxes concerns a constant-speed runner who goes half of a certain distance in 1/2 minute, a fourth of the distance in the next

1/4 minute, an eighth of the distance in the next 1/8 minute and so on. At the end of one minute he has had no difficulty reaching the last point of the distance. Why, then, cannot we say that at the end of one minute the switch of the Thomson lamp has made its last move? The answer is that the lamp must then be on or off and this is the same as saying that there is a last integer that is either even or odd. Since the integers have no last digit, the lamp's operation seems logically absurd.

Another supertask concerns an "infinity machine" that calculates and prints the value of pi. Each digit is printed in half the time it takes to print the preceding one. Moreover, the digits are printed on an idealized tape of finite length, each digit having half the width of the one before it. Both the time and the width series converge to the same limit, so that in theory one might expect the pi machine, in a finite time, to print all the digits of pi on a piece of tape. But pi has no final digit to print, and so again the supertask seems self-contradictory.

One final example: Max Black of Cornell University imagines a machine that transfers a marble from tray A to tray B in one minute and then rests for a minute as a second machine returns the marble to A. In the next half-minute the first machine moves the marble back to B; then it rests for a half-minute as the other machine returns it to A. This continues, in a halving time series, until the machines' movements become, as Black puts it, a "grey blur." At the end of four minutes each machine has made aleph-null transfers. Where is the marble? Once more, the fact that there is no last integer to be odd or even seems to rule out the possibility, even in principle, of such a supertask. (The basic articles on supertasks, by Thomson, Black and others, are reprinted in Wesley C. Salmon's 1970 paperback anthology Zeno's Paradoxes.)

One is tempted to say that the basic difference between supertasks and Zeno's runner is that the runner moves continuously whereas the supertasks are performed in discrete steps that form an aleph-null set. The situation is more complicated than that. Adolph Grunbaum, in Modern Science and Zeno's Paradoxes, argues convincingly that Zeno's runner could also complete his run by what Grunbaum calls a "staccato" motion of aleph-null steps. The staccato runner goes the first half of his distance in 1/4 minute, rests 1/4 minute, goes half of the remaining distance in 1/8 minute, rests 1/8 minute and so on. When he is running, he moves twice as fast as his "legato" counterpart, but his overall average speed is the same, and it is always less than the velocity of light. Since the pauses of the staccato runner converge to zero, at the end of one minute he too will have reached his final point just as an ideal bouncing ball comes to rest after an infinity of discrete bounces. Griinbaum finds no logical objection to the staccato run, even though it cannot be carried out in practice. His attitudes toward the supertasks are complex and controversial. He regards infinity machines of certain designs as being logically impossible and yet in most cases, with suitable qualifications, he defends them as logically consistent variants of the staccato run.

These questions are related to an old argument to the effect that Cantor was mistaken in his claim that aleph-null and c are different orders of infinity. The proof is displayed in Figure 20. The left side is an endless list of integers in serial order.

Figure 20


100 .001

101 .101

1234 .4321

Fallacious proof concerning two alephs

Each is matched with a number on the right that is formed by reversing the order of the digits and putting a decimal in front of them. Since the list on the left can go to infinity, it should eventually include every possible sequence of digits. If it does, the numbers on the right will also catch every possible sequence and therefore will represent all real numbers between 0 and 1. The real numbers form an aleph-one set. Since this set can be put in one-to-one correspondence with the integers, an aleph-null set, the two sets appear to be equivalent.

I would be ashamed to give this proof were it not for the fact that every year or so I receive it from a correspondent who has rediscovered it and convinced himself that he has demolished Cantorian set theory. Readers should have little difficulty seeing what is wrong.

0 0

Post a comment