Size of Infinity

Date: 07/22/97 at 19:35:59
From: John  Cramer
Subject: Size of infinity

How can one infinity be bigger than another infinity? For example, the 
number of real numbers between 0 and 1 is infinite. The number of 
integers greater than 1 is also infinite. Yet the first infinity 
mentioned is bigger than the second one. I don't get it.

Date: 07/25/97 at 17:22:25
From: Doctor Rob
Subject: Re: Size of infinity

This has puzzled many people over the years.  It has to do with the 
way we count.

When you count objects, often you touch (or look at) one of them and 
say "One." Then you touch another and say "Two." You continue touching 
previously untouched objects until you run out them. Then the last 
number you said is the number of objects.

In the abstract, what you are doing is setting up a one-to-one 
correspondence between the objects and a finite set of natural numbers 
of the form {n | 1 <= n <= N}. It is one-to-one because no number is 
used twice, and it is a correspondence because no object is used 
twice.

An extension of this can be used to "count" infinite sets. Again a 
one-to-one correspondence is set up between the set of all natural 
numbers and the set of objects. If all the objects correspond to a 
natural number, and all natural numbers correspond to an object, then 
the set of objects is said to have the same _cardinality_ as the set 
of natural numbers. The same procedure can be used for any two sets.  
If they can be put into one-to-one correpondence, then they are said 
to have the same cardinality. In the case of a finite set, the 
cardinality is just the number of objects. In the case of infinite 
sets, one might naively think that all of them would have the same 
cardinality, and call that "infinity."

In fact, there are infinite sets A and B which cannot be put into 
one-to-one correspondence with each other, but A can be put into 
one-to-one correspondence with a subset of B. In this case, the 
cardinality of A is the same as that of the subset of B, but not the 
same as the cardinality of B. B is said to have larger cardinality 
than A. Notice that in the case of finite sets, the cardinality of a 
proper subset of a finite set is always smaller than the cardinality 
of the whole set, so the analogy is apt.

Your example is like that: the natural numbers cannot be put into
one-to-one correspondence with the real numbers between 0 and 1, 
although they can be put into correspondence with a subset (via 
n <-> 1/(n+1), for example).

The hard part is to *prove* that constructing a one-to-one 
correspondence is impossible in certain cases. That is done by 
contradiction, by making the assumption that one exists, and from that 
deducing a false statement. This means that the assumption had to be 
false to begin with, and the existence is therefore impossible.

In this case, suppose there were such a correspondence.  Make a table 
with the first column containing the natural numbers 1, 2, 3, 4, ..., 
and the second column containing the corresponding real numbers 
between 0 and 1, written out in decimal expansions.  It would take the 
form:

1   0.*********...
2   0.*********...
3   0.*********...
4   0.*********...
... ...

According to the assumption, all real numbers between 0 and 1 will 
appear in some row in the second column. Now we will construct one 
which doesn't appear, as follows. Consider the number D beginning "0." 
and continuing with the digits appearing on the *diagonal* of the 
array of digits in column 2 of the table.  Now pick any number X whose 
digits *disagree* with D in every decimal place, but which contains no 
0 or 9.  (There are 7 or 8 choices for each digit of X, so this is 
easy to do.) Where could it appear on the list? For any natural number 
k, it cannot be in row k, because its k-th digit differs from the k-th 
digit of the number appearing in row k.  This number is not on the 
list in any row. As a result, the assumed one-to-one correspondence 
doesn't exist. Notice that it did not matter in what order we put the 
numbers in column 2 above, the same construction works. Notice also 
that there are huge numbers of X's which can be constructed this way:  
at least 7^k possibilities for just the first k digits to the right of 
the decimal place; and *none* of them is on the list.

(The funny business with 0 and 9 is to avoid the fact that some 
numbers have two decimal expansions: for example, .500000000... = 
.499999999... . The constructed X misses both of these representations 
whenever they exist.)

I hope I haven't boggled your mind with this.  Mostly it wasn't known
until the time of Georg Cantor, in the 19th century.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/