Outer Limits of Reason (18 page)

This subset is different from any subset in the correspondence.

If you (wrongly) claim that there is a
d
₀
in
S
that corresponds to
D
, then look at element
d
₀
:

d
₀
is in
D
if and only if
d
₀
is not in
D.

This is a contradiction and we can conclude that
D
is not in the correspondence. Hence
(
S
) is larger than
S.

It was shown that both (0,1) and
(
N
) are larger than
N.
In fact, a correspondence exists (which I will not describe) between these two sets showing that they have the same cardinality. Since the cardinality of the powerset of a set of size
n
is 2
ⁿ
, and the cardinality of
N
is
₀
, cardinality of
(
N
) is 2
_⁰
. Because this is also the cardinality of the
continuous
interval (0,1), it is also called the “cardinality of the continuum.”

Why did we restrict ourselves to (0,1) only? What about the entire set,
R,
of real numbers? It would seem that the entire set of real numbers is much larger than (0,1). After all, the real numbers also contain the interval (1,2) and (2,3). Don't forget the negative intervals such as (-23, -18). The real numbers contain infinite copies of (0,1). However, following our definition of what it means for two sets to be the same size, we can show that (0,1) is equinumerous to
R
. The formal name for this proof is
proof by stereographic projection
, but I prefer the friendlier
sunshine proof
. The proof is essentially
figure 4.9
.

First take the sun, all bright and shiny, and put it on top of your picture. Then take the interval (0,1) and “bend” it around the sun. Now take the real-number line that represents the set
R
and put it on the bottom of the picture. Realize that the real line goes on to the right and left forever and ever. The description of the correspondence between (0,1) and
R
is as follows: for every point
x
in (0,1), draw a straight line from the sun through
x
and onto
R.
The point where this line crosses
R
will correspond to
x
and will be denoted as
x
. To recognize that this is a good correspondence, all we have to do is realize that two different points
y
and
y'
in (0,1) will go to two different points
y
and
y
′ in
R
. To show that every point
z
of
R
will be in this correspondence, all one has to do is to draw a straight line from the point
z
in
R
back to the sun. This line will pass through a unique point of (0,1). In conclusion, there is a correspondence between (0,1) and
R
and hence they are equinumerous.

We have shown that there are actually two ways of proving that an infinite set is of cardinality larger than
₀
. First, one can make a diagonal argument showing that no correspondence exists between the set and the natural numbers. Second, we can show that there is a correspondence between the set and another set that is already known to have cardinality larger than
₀
.

Several infinite sets with cardinality
₀
have been described. We have also seen several infinite sets with cardinality 2
^₀
. The obvious question is whether there is anything strictly larger than 2
^₀
. The answer is yes. The powerset of a set is strictly larger than the set. From this we can see that the powerset of (0,1), denoted
((0,1)), will not be in correspondence with (0,1). That is, the set of subsets of the unit interval (0,1) will be larger than (0,1). This set will have cardinality 2
^2
₀
It is difficult to wrap one's mind around such a set. Try to write down some of the elements.