Outer Limits of Reason (13 page)

Section 4.1
is concerned with the basic language of sets. I restrict myself to the familiar world of finite sets and give a nice definition that determines when two sets are the same size. In
section 4.2
I take this definition that works so well with finite sets and see what happens when we move to infinite sets. The strange world of infinity starts making life more interesting. The core of this chapter is
section 4.3
, where we encounter the different levels of infinity. Along the way, we will learn about a powerful proof technique called diagonalization. I close with
section 4.4
, where more advanced and philosophical topics are discussed.

4.1  Sets and Sizes

The ideas of infinity are expressed in the language of sets. A set is a collection of distinct objects. The objects can be anything and everything (including other sets). The objects in a set are called elements or members of the set. Sets can be denoted by braces (curly brackets) around their elements. So, the set

{a, b, c}

has three elements, which are the letters
a
,
b
, and
c
. We can talk about the set of students in a class, the set of red cars, the set of U.S. residents, the set of fractions, and so on.

There are different ways of denoting a set. We can list the elements of the set, such as

{dogs, cats, parrots, fish, snakes},

or we can describe the same set by giving a description:

{
x: x
is one of the five most popular household pets}.

This is read as “The set of all
x
, such that
x
is one of the five most popular household pets.” Another example is

{3, 5, 7, 9, 11}.

This is the same set as

{
x: x
is an odd whole number greater than or equal to 3 and less than 12}.

Sometimes, when talking about infinite sets, I will use an ellipsis (. . .) to mean that the sequence continues. For example, the prime numbers can be written as

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

Capital letters will be used as names to describe certain sets:

D = {1, 3, 5, 7, 9, 11, 13, 15, . . . }.

Two sets are equal if every element of one set is an element of the other set. So if

F =
{
x: x
is a whole odd number}

it is obvious that

D = F.

Certain sets will be subsets of other sets. It is obvious that the set of women in a class is a subset of the set of all students in the class. This is because every woman in the class is a student in the class. In general, given two sets,
S
and
T,
we say that
S
is a
subset
of
T
if every element of
S
is an element of
T.
Notice that a subset of
T
can be equal to the entire set
T
.
S
is a
proper subset
of
T
if
S
is a subset of
T
but is not equal to
T
. That is, a subset is not proper if it could be the same as the whole set.
S
is a proper subset of
T
if there is some element of
T
that is not an element of
S
. In terms of number of elements,
S
is a subset of
T
if
S
has fewer or the same number of elements as
T
.
S
is a proper subset of
T
if it has strictly fewer elements than
T
. This obvious fact about finite sets will be a sticking point when we meet infinite sets in the coming sections.

There is a special set that has no elements. This set is called the empty set and is denoted by
. For any set
S,
the following statement is always true:

Every element of
is also an element of
S.

After all, there are no elements in
.
So
is a subset of
S
.

For any set
S,
we will be interested in the set of all subsets of
S
, which is called the
powerset
of
S
and is denoted as
(
S
). For example, if
S
=
{
a, b
}, then

(S) = {
, {a}, {b}, {a, b}}.

Notice that this set has four elements of which three are proper subsets of
S.
If there is a third element in
S
, such as
S
=
{
a, b, c
}, then the powerset has the same subsets as before, namely
, {
a
}, {
b
}, {
a, b
}, but now each of those subsets can also contain
c
and so we have the subsets {
c
}, {
a, c
}, {
b, c
}, {
a, b, c
}. Hence we have

({
a
,
b
,
c
}) = {
, {
a
}, {
b
}, {
a
,
b
}, {
c
}, {
a
,
c
}, {
b
,
c
}, {
a
,
b
,
c
}}.