Outer Limits of Reason (14 page)

That is, by adding
c
to
S
we double the number of subsets. For a two- element set, the powerset has four elements. For a three-element set, the powerset has 2 × 4
=
8 elements. For a four-element set, the powerset has 2 × 8
=
16 elements. In general, the powerset of an
n
-element set has

elements. So, usually the powerset of a set is much larger than the set.

When are two sets the same size? Consider the set

S = {
a
,
b
,
c
,
d
,
e
}

and the set of household pets

T = {dogs, cats, parrots, fish, snakes}.

It is obvious that these two sets are the same size: they both have five elements. However, let us examine this apparent fact in another way. Say that
S
and
T
are the same size because we can pair off every element of
S
with a unique element of
T
. That is,
S
and
T
are the same size because a correspondence exists that relates every element of
S
with a unique element of
T
and vice versa. For each element of
S
there is a unique mate in
T
and for each element of
T
there is a unique mate in
S.
This pairing or correspondence can be viewed as follows:

There might be other correspondences between the two sets—for example,

In fact, both
S and T
can be shown to correspond to the set

{1,2,3,4,5}.

With these correspondences we are confident that all of these sets have five elements.

This simple idea is at the core of this chapter. We say that two arbitrary sets,
S
and
T,
are
equinumerous
or the
same size
if such a correspondence exists between them. The sets will be deemed to have the same
cardinality
.

Examples of equinumerous sets abound:

• The set of human hearts in the world is the same size as the set of people in the world. (Note that this would not work with ears because people generally have two ears.)

• The set of states in the United States

{Alabama, Alaska, Arizona, . . . , Wisconsin, Wyoming}

can be put into correspondence with the set of state capitals in the United States

{Montgomery, Juneau, Phoenix, . . . , Madison, Cheyenne}

which can also be put in correspondence with the set

{1, 2, 3, . . . , 49, 50}.

• The set of ISBN codes can be put into correspondence with the set of published books.

The world of finite sets and correspondences between them is pretty straightforward. The definition stated for two sets to be of the same size is definitely reasonable. Now let us take a few small steps into the realm of the infinite.

4.2  Infinite Sets

David Hilbert (1862–1943), the greatest mathematician of his generation, told an interesting tale. Imagine owning a hotel with an infinite number of rooms. Let us call it “Hilbert's Hotel.” Business is good and every one of the infinite rooms is occupied. Along comes a car with another guest who needs a room. You don't want to send the guest away on a cold blustery night, but all your rooms are full. What to do? Hilbert gave a suggestion: get on your hotel loudspeaker and have every one of the infinite guests move to the next room. So the guest in room 57 moves into room 58 and the guest in room 53,462 moves to room 53,463. In general, every guest in room
n
moves into room
n
+
1. This leaves room 1 open for the extremely grateful new guest.

Let's go on with the tale. Just as all the guests have gotten settled in their new rooms and are blissfully sleeping, a bus pulls up in front of Hilbert's Hotel with an infinite number of passengers, each demanding their own room. Every one of your infinite rooms is occupied and you are in desperate need of an infinite number of empty rooms. What is an honest hotel manager to do? Again, Hilbert has some good advice: get on your handy-dandy hotel loudspeaker and tell every guest to go to the room whose number is twice the number of their present number. That is, the guest in room 57 goes into room 114 and the guest in room 53,462 goes into room 106,924. In general, every guest in room
n
goes to room number 2
n
. After this, all the even-numbered rooms will be occupied and all the odd-numbered rooms are empty and waiting for your tired bus passengers.

Notice that these tricks would not work for one of those boring standard hotels with a finite number of rooms. It's only in Hilbert's cool hotel with an infinite amount of rooms that we can move people without worrying about losing any guests. What Hilbert really shows in the first case is that there is a correspondence between the infinite set of rooms {1, 2, 3, 4, 5, . . .} and a proper subset of that set: {2, 3, 4, 5, . . .}. In the second case, Hilbert shows that there is a correspondence between the set of rooms {1, 2, 3, 4, 5, . . .} and the proper subset {2, 4, 6, 8, 10, . . .}. It's these strange counterintuitive correspondences that we are going to explore in this section.

Rather than telling stories about fictitious hotels, let us work with some real infinite sets. There are many examples of infinite sets, but these sets must contain more than physical objects because there are only a finite number of physical objects in the universe. Many other concepts like numbers can form infinite sets. There are many common infinite sets of numbers:

• Natural numbers,
N =
{0, 1, 2, 3, . . .}

• Whole numbers or integers,
Z =
{. . . , –3, –2, –1, 0, 1, 2, 3, . . .}

• Rational numbers or fractions,
Q
= {
m/n: m
and
n
in
Z
and
n
is not 0}

• Real numbers,
R

The natural numbers are a proper subset of all whole numbers. Every whole number
n
can be thought of as the fraction
n/1
and so the whole numbers can be regarded as a proper subset of all rational numbers. Finally, the real numbers are the set of all numbers, even those that cannot be described as fractions. It has been known for over 2,500 years that there are certain numbers, such as √2,
e
, –
π
, and √5, that cannot be written as fractions. Such numbers are called “irrational”—that is, “not rational” or “not reasonable.”
²
The real numbers,
R
, contain all the rational and irrational numbers. So the rational numbers are a proper subset of the real numbers.

Consider the set of even numbers

E
= {0, 2, 4, 6, . . .}.

Every even number is a natural number, so
E
is clearly a proper subset of
N,
the natural numbers. In fact, one could say that there are twice as many natural numbers as there are even numbers. After all, the natural numbers consist of the even numbers
and the odd numbers!
But we will not follow our intuition of sets and proper subsets. Rather, we will follow the definition of being equinumerous from the last section. A correspondence exists between the natural numbers and the even numbers: simply make every natural number,
n
, correspond to the even number 2
n
:

This shows that
N
and
E
are the same size. How can that be? How can there be just as many natural numbers as there are even numbers? What about the odd numbers? How can a part be the same size as a whole?

Where did we go wrong? The answer is that we did not go wrong. The same reasoning that was used for finite sets was used here. However, for finite sets, having the same size follows our intuition. After all, our intuition was developed by looking at the world and its finite sets. For infinite sets, logic dictates that our naive intuition is no longer valid and needs to be modified. Galileo Galilei (1564–1642) was the first to write of this strangeness about infinite sets. He showed that an infinite set can be equinumerous to a proper subset of itself. In the 400 years since Galileo, this new definition has worked its way into all of mathematics and physics. We cannot simply ignore it because it goes against our intuition. Rather, these definitions are crucial to the models we use in interpreting the universe and are used in scientific predictions. We must understand and accept the definition. Our intuition needs to be adjusted.

On to some more infinite sets! Consider the set
S
of square numbers—that is, numbers that are equal to the product of a whole number with itself:

S
= {0, 1, 4, 9, 16, 25, . . .}.

This set is an infinite set and it is also a proper subset of
N,
the natural numbers. There are far fewer square numbers than even numbers: in the first hundred natural numbers, there are only ten square numbers. However,
S
can also be put into a correspondence with the natural numbers:

This correspondence shows that the natural numbers and their proper subset of square numbers are equinumerous. They have the same cardinality. Can we assign a number to describe the amount of elements in these sets? Obviously no finite number will do. Cantor denoted the amount or cardinality of these infinite sets by the symbol
_0,
pronounced “aleph-null.” Aleph is the first letter in the Hebrew alphabet. All sets that are equinumerous to
N,
the natural numbers, have cardinality
₀
and are called
countably infinite
sets. It is important to realize that we cannot complete counting such infinite sets. Nevertheless, we can at least begin to count them. By looking at a correspondence with the natural numbers, we can say what the 0th element is, what the 1st element is, what the 2nd element is, and so on.