Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search