Outer Limits of Reason (15 page)

There are other sets with this cardinality. Remember that a number is prime if it is more than 1 and only divisible by 1 and itself. Consider the set of all prime numbers:

P
= { 2, 3, 5, 7, 11, 13, . . . }.

Even though there are seemingly far fewer prime numbers than natural numbers, a correspondence still exists:

This shows that
P
is equinumerous to the natural numbers. How do we describe this correspondence? What is the 42nd prime number? No simple formula gives us this information. Nevertheless, even though it is not easy to describe a correspondence, all that we require is that a correspondence
exists
that shows that
P
is of cardinality
_0.

So far, all the infinite sets we have discussed are proper subsets of the natural numbers. What about sets that are seemingly larger than the natural numbers? Are these sets, in fact, larger than the natural numbers? Consider the set of whole numbers

Z
= {. . . , –3, –2, –1, 0, 1, 2, 3, . . .}.

The natural numbers are a proper subset of
Z
. However,
Z
also contains the negative whole numbers. How can we possibly make a correspondence between
N
and the set
Z
that contains positive and negative natural numbers? Luckily, very smart people like Cantor worked on this problem and were able to find a simple correspondence, as shown here:

By cleverly splitting
N
into even and odd numbers, we make the odd numbers of
N
correspond to the positive integers of
Z
, while the even numbers of
N
correspond to the negative integers of
Z
. Since we will never come to the end of the odds or evens, every number in
Z
will be paired. This is exactly what we did in Hilbert's hotel, where we made the even-numbered rooms for the infinite set of old guests and the odd-numbered rooms for the infinite set of new guests.

Let us look at a really large set. Consider the set
N
×
N
of ordered pairs of natural numbers. That is the set of pairs <
m,n
>, where
m
and
n
are natural numbers. For every
m,
there is a copy of natural numbers
:

<
m
,0>, <
m
,1>, <
m
,2>, <
m
,3>, . . . .

Since there are infinitely many
m
, the set
N
×
N
has infinitely many copies of
N.
The integers,
Z,
had two copies of
N
, one for the positive numbers and one for the negative numbers. In contrast, this set
N
×
N
has
infinitely
many copies of
N.
Our intuition tells us that this set has far more elements than
N
. Our intuition is wrong! Cantor was a very intelligent man and was able to find a correspondence between
N
and
N
×
N
. One can describe this correspondence as follows:

To see this correspondence clearly, think of the natural numbers as a long line of numbers, as in
figure 4.1
.

Writing the set
N
×
N
as in
figure 4.2
, let the natural numbers “snake” their way through
N
×
N
in a zigzag pattern.

Since these sets are infinite sets and we only have a finite amount of paper, we cannot display the entire correspondence. However, following this pattern, every ordered pair, including <303, 1227>, will eventually correspond to some natural number in
N
. For obvious reasons, this proof is sometimes called the
zigzag proof
. In summary, the set
N
×
N
is also equinumerous to
N
and has cardinality
₀
.

What about
Q
, the set of rational numbers? Surely there are more fractions than natural numbers! After all, every
n
in
N
is simply
n/
1 in
Q.
So
Q
has a copy of
N
inside it:

0/1, 1/1, 2/1, 3/1, . . . .

But
Q
also has

n
/2,
n
/3,
n
/4, . . . .

Let us not forget negative fractions:

–
n
/1, –
n
/2, –
n
/3, –
n
/4, . . . .

In addition, notice that between any two fractions, say 3/5 and 4/5, there is another fraction: 7/10. We can go on with this: between 3/5 and 7/10, there is 13/20. It would seem obvious that there are far more rational numbers than natural numbers. However, by now you should be expecting the unexpected. It might seem as though there are a lot more rational numbers than natural numbers, but, in fact, they are the same size. We will show this by exhibiting a correspondence between
N
and
Q
, as in
figure 4.3
.

Again, the natural numbers “snake” around the fractions and eventually hit every fraction. This proof is sometimes called the
necklace proof
. Can you see why?

However, there is a slight problem here. There are repetitions of rational numbers in our listing in
figure 4.3
. The rational number 4/7 has the same value as 8/14. So are we really making a correspondence with the set of rational numbers? In truth, we are doing something harder: we are making a correspondence between
N
and a set
larger
than rational numbers. There are, however, ways of making correspondences with only the rational numbers, simply by letting our snake skip over fractions that are already hit.

In conclusion, many sets that seem infinitely larger than the natural numbers are, in fact, equinumerous with the natural numbers. Is there any infinite set that is actually larger than the natural numbers?

4.3  Anything Larger?

While reading the last section, one can come to the conclusion that, with enough cleverness, every infinite set can be put into correspondence with the natural numbers. Cantor also thought this for a while . . . but then he looked at the real numbers.