Class 6

The uncountability of the real numbers

The examples of infinite sets that we have seen so far might suggest that all infinities are countable. This seems to be what Galileo believed, without going into it very deeply. But in 1874 Georg Cantor found an infinite set that is bigger than countable: a bigger, uncountable infinity. The set in question is the set of real numbers between 0 and 1. Here "real" means all numbers, whether rational or irrational. (We already know that the rational numbers between 0 and 1 are countable.) There is a convenient representation of elements of this set: a typical one might be 0.1426829402897538..., i.e., each such number has a decimal fraction representation, which we may take to go on forever, even if it is a number like 0.5000000000000... which goes on forever in a particularly simple way. There is a subtlety, which is not too crucial to the argument, but kind of fun to think about. The rational number 1/2, whose decimal fraction representation we just looked at, namely 0.50000000... can also be represented as 0.499999999999..., where the 9's go on forever. WHAT?! you must be thinking. That can't be 1/2. Surely it is less than 1/2. But no, it is really 1/2. To see this, try subtracting it from 0.50000000000.... You may be thinking you would get something like 0.0000000000001, but which place has the '1'? If you truncate the decimal fractions at the 20th place, and subtract, then the 1 is in the 20th place, but if you truncate in the 30th place, then it is in the 30th place, and of course truncating means we are just using a good approximation: to be more accurate, we should go out even farther. The '1' moves farther out the more accurate we are. That means the difference between these two numbers gets closer to zero the more accurately we compute it. So what is the actual difference? It is less than any positive number. That means it is zero!

In order that each real number have a unique decimal representation, we choose not to include decimal fractions which are all 9's after some position: rather we will use the equivalent representation which has all 0's. For example, 0.499999999... will not occur among our numbers. We will use 0.500000000... instead.

To show a set is countable, you exhibit a way of counting it, i.e., listing it. To show a set is uncountable, you must show that that cannot be done. That is what Cantor did. He showed that no list could contain all the real numbers between 0 and 1. The method is much like Euclid's proof that no finite list could contain all the primes, except that Cantor of course used an infinite list: like Euclid, he assumed there was a list, and showed it led to a contradiction. So we follow him and assume that there is a list containing all the decimal fractions, which would have to look something like

1	0.412535286438453485...
2	0.582938752320309532...
3	0.340859403890349589...
4	0.928347584349857348...
5	0.839453002439549350...
6	0.483974583945834953...
7	0.897405723293409855...
8	0.284634530498503934...
....	....

If the real numbers were countable, every one of them would have to occur somewhere in the list. But Cantor now produces a number which is definitely not in the list. Rather, he constructs such a number, digit by digit. The first digit after the decimal point is chosen to be different from the first digit in the first number of the list (which is a '4' in our example) and also different from 0 and 9, so that we never run into the problem of all 9's, or all 0's, etc. Thus we could take the first digit to be 3, for example. Now the 2nd digit is taken different from the 2nd digit of the 2nd number, which is '8' in the list above (and it should also be different from 0 and 9). We could take 7, for example. The 3rd digit is taken to be different from the 3rd digit of the 3rd number, which is '0' in our example -- let us take the new 3rd digit to be 2. So far we have constructed 0.372 ... The process goes on in this way forever. It is clear that in this way we build a real decimal fraction which differs in the jth digit from the jth number in the list, for all places j. But is that decimal fraction in the list? NO! Any position n where you might think to find it turns out not to have it: the number corresponding to n in the list is different from our number: in the nth place, even if nowhere else. Our number is nowhere to be found. It is not in the list. Thus no list could contain all the decimal fractions, i.e. all the real numbers.

Thus the real numbers between 0 and 1, which we might identify with the points of a number line segment going from 0 to 1, represent a new kind of infinity, bigger than countable. This number is sometimes called "the power of the continuum," or, with its own symbol,   (using the Hebrew letter "aleph"). The number of elements in a countably infinite set is called . If you recall, Simplicio worried that a longer line, say the interval (0,2), would have an even greater infinity of points than the interval (0,1), but we can find a one-to-one correspondence between points in the long line and points in the short line which proves that they have the same number of points, in each case: namely every x in (0,1) corresponds to 2x in (0,2), and every y in (0,2) corresponds to y/2 in (0,1). This correspondence shows the cardinality of the two sets is the same.

The cardinality of the irrationals

We know the number of rational points in (0,1) is . How about the irrational points? Together these two sets make the real numbers in (0,1), which has points. If the irrational points were countable, the union of rational and irrational would be countable, but it isn't. Thus the irrational points alone must be uncountable, like the reals. It is natural to wonder if the irrationals also have cardinality , like the reals, or whether they might represent some new infinity. The answer turns out to be that the irrationals have the same cardinality as the reals, . It is not at all easy to find a 1-1 correspondence between the irrationals and the reals, though! The best proof makes use of a theorem proved in 1896 by Ernst Schroeder (but conjectured by Cantor), namely that two sets A and B have the same cardinality if you can find a 1-1 correspondence between all of A and a subset of B, and between all of B and a subset of A. That seems to say that A could "fit into" B, so A cannot be bigger than B, and also B could "fit into" A, so B cannot be bigger than A. Thus they would have to be equal? That is just a hope, of course, not a proof of anything, but it turns out to be true! With the Schroeder theorem, one can then fit the irrationals into the reals (they already are there, as a subset of the reals), and then cleverly fit the reals into the irrationals! That last step is done, for example, as follows. Take the real number 0.33333333...., and let it correspond to 0.30311300031111300000... The digits of the real number are being padded with 0's and 1's in a way that cannot possibly repeat, because the padded sequences of 0's and 1's get longer and longer, so this is an irrational number. The subset of irrational numbers with 0's and 1's in these places is thus in 1-1 correspondence with all the reals. Since the irrationals fit into a subset of the reals, and the reals fit into a subset of the irrationals, they have the same cardinality, , by the Schroeder theorem. Thus "most" numbers between 0 and 1 are irrational, which means we are unable to write most numbers! The arithmetic we do uses only a very tiny, special set of numbers, when looked at in this way.

The continuum hypothesis

I hope you are surprised that there are two different infinities! It is a very odd thing. But maybe this is not the end! There could be even more infinities, different from these, perhaps. Cantor suspected there was no "intermediate" infinity, larger than but smaller than , but he was unable to prove it. In 1900, David Hilbert, in a famous list of problems for the new century, put Cantor's conjecture, called the "continuum hypothesis," as Problem #1. This problem was not solved until 1963 (Paul Cohen, Stanford University), and the answer was so unexpected that I can't exactly tell you how it came out! I will just have to say that it was neither yes nor no.

Larger infinities

Although Cantor never found an infinity between and , he did find more infinities. They are even larger than the continuum, ! Surprisingly, they are quite easy to describe. They generalize something which you can easily visualize in the case of finite sets, called the power set of a set A. The power set of A is the set consisting of all subsets of A. This is best illustrated by an example. Suppose A={a,b,c} contains 3 elements. Subsets of A are sets which contain some of a, b, and c, possibly all, and possibly none. Let us just list them: the subsets of A are {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. The first one in the list is the "empty set," and it is convenient to consider it a subset. The set of all subsets of A is then P(A)={ {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }. It is itself a set, and its elements are sets: a set of sets! The cardinality of A is 3, because A has 3 elements. The cardinality of the power set P(A) is 2^3 = 8, the 3rd power of 2. There are 8 different subsets of A. That is because when you make a subset of A, for each element of A you get 2 possibilities: either it is in the subset or it is not. The number of different ways to choose subsets is 2x2x2, one factor 2 for each element of A. The empty set is where you say "no" to each element. When you say "yes" to each element you just get A back again, now considered as a subset of itself! Other choices for "yes" and "no" give the other subsets in P(A). It is clear that P(A) has larger (finite) cardinality than A itself, because 2^n is bigger than n for any positive integer n.

Cantor tried this idea on sets A = {a,b,c,d,...} with infinite cardinality. (I will describe the idea as if A were countable, because it is easier to write out examples in this case, but the argument is the same even if A is the continuum, for example.) He was able to show that A and P(A) do not have the same cardinality, so they must be different infinities. In fact P(A) is a bigger infinity than A, because A can fit into P(A) (think of the subsets {a}, {b}, {c}, ... in P(A), which correspond to the elements of A). But P(A) cannot fit into A, because that would imply there exists a one-to-one correspondence between A and P(A), which Cantor shows is impossible. Here is Cantor's argument (it takes a familiar form): suppose you could set up such a correspondence. Then to every element of A you would have a corresponding subset of A. It might look like this:

a	{b,c}
b	{}
c	{x,y,z}
d	{a,d}
e	{b,c,d,e,f,g,h}
f	{a}
g	{b,d}
h	{r,s}
...	...

Now if you look in the first column, you find that some of the elements of A there correspond to subsets of which they are members. That is not true of a, because a corresponds to the subset {b,c}, and it is not a member of that. But it is true of d: d corresponds to the subset {a,d}, and d is a member of that. Elements of A which DO belong to their corresponding subset we shall call "ins," and elements of A which DO NOT belong to their corresponding subset we shall call "outs." In the example above, a,b,c,f,g,h,... are "outs", and d,e,...are "ins". Now we consider the "outs," which together constitute a very special subset of A. That subset should appear in the second column above, which was supposed to include ALL the elements of P(A), i.e., ALL subsets of A, and so, certainly, the subset of the "outs." What element of A would be in the first column, corresponding to the subset of "outs"? Would it be an "out"? NO! The defining property of "outs" is that they are NOT in their corresponding subset, in this case not in the "outs", so it obviously can't be an "out." Therefore it ought to be an "in", but that is also impossible! The "ins", by definition, must belong to their corresponding subset, and the subset corresponding here is precisely the "outs," which does not contain even a single "in." Thus there is NO element of A which could correspond to this strange subset, and hence the correspondence is not 1-1. There is at least one subset of P(A) left out.

This remarkable argument proves the cardinality of P(A) is bigger than the cardinality of A. Suppose we take A to be N, the natural numbers, with cardinality . Then, as you might have suspected, the cardinality of P(N) is . And what about the power set of that, P(P(N))?? Its cardinality must be an even larger infinity, denoted , etc. so there is a sequence of infinities, each larger than the previous one, going on forever!

Assignment 6

This is again a kind of game, illustrating the proof of Cantor's theorem above. Choose a finite set A and set up a correspondence between the elements of A and some of the elements of P(A). (Of course you will run out of elements of A before you run out of elements of P(A), so there will be elements of P(A) left over: P(A) is too big.) Be a little creative so that your answer won't be exactly like anyone else's. Determine the subset of "outs" in your correspondence. Look for that subset in your correspondence, and point out that it is not there! (This is no accident: it couldn't be there.) Do this twice, making different choices.