## Proof That Not All Infinities Are The Same Size

The proof is as follows: we count by matching the natural numbers
to some set. For example, the set:

has three elements in it; we match each bullet with a natural number:
and the last number is 3.
In infinite sets, we do the same thing. For example, the number of
squares and the number of natural numbers is the same. To show this
rather odd result, consider the following matching:

1 4 9 16 25 36 ...
^ ^ ^ ^ ^ ^
| | | | | |
v v v v v v
1 2 3 4 5 6 ...

You can continue this matching; as you can see, every natural number
gets a unique square, so the number of squares and the number of
natural numbers is the same. (Another way of putting this is that
every natural number has a square, and every square is associated with
a natural number).
How about the rational numbers? It might seem that the set of all
rationals, like 3/8 and 5/9 and 12321/98732 would be much larger than
the set of natural numbers. However, you can match them up. The
proof is fairly simple, but difficult to format in html. But here's a
variant, which introduces an important idea: matching each number with
a natural number is equivalent to writing an itemized list. Let's
write our list of rationals as follows:

- 0/1
- 0/2
- 1/1
- 0/3
- 1/2
- 2/1
- 0/4
- 1/3
- 2/2
- 3/1

and so on. Notice that first we list all the fractions whose
numerator and denominator add to 1, then those that add to 2, then
those that add to three, etc. Every fraction is somewhere on this
list (and a little elementary arithmetic sequence calculation can tell
you *exactly* where on the list a fraction like 12321/98732 would
appear...an exercise I'll leave to the alert reader).
Now for the real numbers. Cantor's first proof is complicated, but
his second is much nicer and is the standard proof today. Again,
*suppose* we could list every one of the real numbers. A list
might look like this:

- 0.3249187....
- 1.3289713....
- 3.1415926....
- 2.7182813....
- 0.2349873....
- 0.3987423....

and so on. If we suppose this list is complete, we can write a real
number that is *not* on the list. We'll make the real number
this way: here's our list again, with certain numbers highlighted:
- 0.
**3**249187....
- 1.3
**2**89713....
- 3.14
**1**5926....
- 2.718
**2**813....
- 0.2349
**8**73....
- 0.39874
**2**3....

Now, our new number will be constructed in the following manner: take
each highlighted number, and add 1 to it. That will be the
corresponding decimal digit in our new number. (If the result is 10,
use 0). Thus, the new number is:

0.432393...
which is *different* from every number on the list: it's
different from the first number in the first decimal place; from the
second in the second decimal place, and so on. So it's not on our
supposedly complete list of numbers. Thus our list is not complete,
and **no** list of real numbers would be complete.
How about the points in the plane? You can describe any point in the
plane with two coordinates. Suppose we're talking about the point
(0.2132... , **0.9879...**). This can get matched to the real
number 0.2**9**1**8**3**7**2**7**... Thus, every point in
the plane is "counted" by a real number. An obvious
extension says that the number of points in n-dimensional space is the
same as the number of points on the line segment (0,1).

For a nice proof (with pictures) of these ideas, I can think of no
more accessible source than George Gamow's *One, Two,
Three...Infinity*. The science in the book is hopeless dated, but
the mathematics (which make up the first and last sections) are still
superb.

Return to Jeff's home page