Outer Limits of Reason (19 page)

Of course, there is no reason to stop there. We can go on using the powerset function to describe sets of even higher cardinality. None of the sets in different levels of infinity can be put into correspondence with each other.

4.4  Knowable and Unknowable

The ideas of set theory described in the previous three sections are totally reasonable and rational. Unfortunately there is one little fatal flaw in them: set theory, as we have expressed it so far, is
inconsistent
. That means that with the language of set theory that we have used, we can formulate contradictions. This was first pointed out in a letter dated June 16, 1902, from Bertrand Russell (1872–1970) to Gottlob Frege (1848–1925) in which a simple contradiction in basic set theory was first illustrated. This contradiction is called Russell's paradox. Although we've already encountered this paradox in 
section 2.2
, it is worth reminding ourselves what it is all about.

One can discuss many sets. Consider the set

H
= {
a
,
b
, {
c
,
d
}}.

This set consists of three elements. Two of the elements are the letters
a
and
b,
and one of the elements is a set {
c,d
}. Now consider the set of

J
= {
a
,
b
,
J
}.

This set also contains three elements but one of its elements is
itself
! Now consider the following set, which we call
R
for Russell:

R
= The set of sets that do not contain themselves.

So the above
H
is an element of
R
but the above set
J
is not an element of
R.
Now ask the following simple question:

Is
R
an element of itself?

If
R
is an element of
R
, then according to the requirements of being an element of
R
, it must be that
R
is not an element of itself. In contrast, if
R
is not an element of itself, then it satisfies the requirement of being in
R
and so
R
is in
R.
Hence we have a contradiction, and we conclude that the naive form of set theory that we described is inconsistent. This was a tremendous blow to the researchers at the time. A contradiction within a system renders it useless.

This is a paradox. We made an assumption and were led to a contradiction. The subtle assumption we made is that for every description there is a set of elements that have the objects described. This works most but not all of the time. For example, if I think of the property of red, then I can form the set of all red things. With a description of pink Cadillacs there is a set of pink Cadillacs. But the description “does not contain itself” cannot correspond to a set of things that does not contain itself. This will lead to a contradiction. We must be careful.

To avoid contradictions such as Russell's paradox, researchers tried to formalize some of the notions of set theory and put some restrictions on the type of sets that can exist. This was done by developing a system of axioms that are self-evident and by using these axioms to generate theorems about sets.

One axiom system was formulated by Ernst Zermelo (1871–1956) and Abraham Fraenkel (1891–1965). This system, which came to be known as
Zermelo-Fraenkel set theory
, is the most important in the field.
⁶
The axioms of Zermelo-Fraenkel set theory are as follows:

1.
Axiom of extensionality
   Two sets are the same if they have the same elements.

2.
Axiom of pairing
   For any
x
and
y
, there exists a set {
x,y
}.

3.
Axiom of subset selection
(also called
axiom of restricted comprehension
)   If
X
is a set, and φ is a property that describes certain elements of
X,
then a subset
Y
of
X
exists containing only those
x
in
X
that satisfy the property—that is,

Y =
{
x
in
X|
φ(
x
) is true}.

(This almost says that if you have a property, say “redness,” then you have a set of all things that are red. However, we need to restrict this axiom because otherwise there will be trouble with Russell's paradox by simply looking at the property of “not containing itself.” We cannot talk of a subset of “everything.” Rather, we can only talk of a subset of something. So for a property φ, we cannot say that

Y =
{
x |
φ(
x
) is true}

is a set. Rather, we must restrict this to a particular set
X.
)

4.
Axiom of union
   The union of a set of sets is a set.

5.
Axiom of powerset
   For any set
X
, the powerset of
X
is also a set.

6.
Axiom of infinity
   There exist sets with infinitely many elements.

7.
Axiom of replacement
   If
F
is a function—that is, a way of assigning elements from one set to another set—and
X
is a set, then
F
(
X
), the set of values of
F,
is also a set

F
(
X
)
=
{
F
(
x
)
|x
in
X
}.

8.
Axiom of regularity
(also called the
axiom of foundation
)   There is no infinite regression of a set that contains a set that contains a set . . . In technical terms, every nonempty set
X
contains a member
Y
such that
X
and
Y
are not the same sets.

An interesting philosophical question must be posed. Zermelo-Fraenkel set theory restricts us from discussing or accepting certain sets as legitimate. We can only consider certain collections as sets and are not permitted to consider other collections as sets. Does this mean that the other collections do not exist? Are they not also sets? Yes, it is good to steer clear of contradictions, and we like such error-free systems, but are we being truthful as to what really exists? Are we throwing away the baby with the bathwater?

The amazing fact about Zermelo-Fraenkel set theory is that the vast majority of modern mathematics can be formulated with sets and these few simple axioms. In a comprehensive encyclopedia of mathematics, we find the following observation: “Nowadays, it is known to be possible, logically speaking, that current mathematics, almost in its entirety, can be derived from a single source: the theory of sets.”
⁷
In other words, most of mathematics can be seen to be built on the foundation of these few axioms. Most working mathematicians usually do not think about the axioms, nor do they care if their work can be put into the language of Zermelo-Fraenkel set theory. Nevertheless, with enough effort, their work can be stated within the language of Zermelo-Fraenkel set theory. From this important position, the axioms of Zermelo-Fraenkel set theory can be seen as the axioms of all of mathematics and hence the axioms of exact reasoning itself.

The obvious question is whether Zermelo-Fraenkel set theory is consistent. After all, one reason for putting set theory into axioms is to make sure that we steer clear of problems like Russell's paradox and other contradictions. It would be nice to know that no contradictions can be derived from these axioms. Concerning consistency, there is good news and there is bad news. The good news is that the Zermelo-Fraenkel set theory has been around for about a century and no one has derived any contradiction yet. Nor does it look like anyone will in the future. The bad news is that one of the consequences of Gödel's famous incompleteness theorems (which we will meet, in detail, in sections 
9.4
and 
9.5
) is that the consistency of Zermelo-Fraenkel set theory is not provable within standard mathematics. And so we cannot be absolutely certain that Zermelo- Fraenkel set theory and all of the modern mathematics that it entails is consistent.
⁸

Let's examine some topics about what can and cannot be proved using Zermelo-Fraenkel set theory. In
section 4.2
we showed that there are many sets that are equinumerous to the natural numbers
N
. In
Section 3
we showed that there are many sets that are equinumerous to the set (0,1) and that these sets are strictly larger than
N
. The obvious question arises: Are there any sets that are between
N
and (0,1)? That is, does there exist an infinite set
S
such that
N
is strictly smaller than
S
and, in turn,
S
is strictly smaller than (0,1)? What we are really asking is whether there is something between
₀
and 2
^₀
. This is a perfectly simple question. All we want to know is if a certain set of a particular size exists. We do not even care what the elements of the set are. Our only concern is the size of the set. Cantor was the first to ask this question in the 1880s. He believed the answer was no and formulated this conjecture as the “continuum hypothesis”:

There does not exist a set whose size is strictly between
N
and (0,1).

Despite much effort, Cantor was unable to prove this conjecture. In 1900, David Hilbert gave a famous speech in which he listed twenty-three hard problems that were challenges to be solved in the twentieth century. The continuum hypothesis was number one.

In 1940, Kurt Gödel (1906–1978) showed that (assuming Zermelo-Fraenkel set theory is consistent) the continuum hypothesis is consistent with the axioms of Zermelo-Fraenkel set theory. This means that one cannot derive a contradiction from the axioms of Zermelo-Fraenkel set theory by simply adding an axiom stating that the continuum hypothesis is true. Another way of saying this is that there is a way of interpreting the axioms such that the continuum hypothesis is true and there
does not
exist a set of intermediate size.

In 1963, Paul Cohen (1934–2007), who once studied at Brooklyn College, gave a final answer to the eighty-year-old problem. He showed that (assuming Zermelo-Fraenkel set theory is consistent) the negation of the continuum hypothesis is consistent with the axioms of Zermelo-Fraenkel set theory. This means that one cannot derive a contradiction from the axioms of Zermelo-Fraenkel set theory by simply adding the axiom stating that the continuum hypothesis is false. Another way of saying this is that there is a way of interpreting the axioms such that the continuum hypothesis is false and there
does
exist a set that is strictly between
N
and (0,1).

With the results of Gödel and Cohen, one says that the continuum hypothesis is “independent” of the axioms of Zermelo-Fraenkel set theory. That means that the axioms cannot prove or disprove it. There is no way of answering these questions with the axioms of Zermelo-Fraenkel set theory, or any other equivalent set theory. With this independence from the axioms, one can go farther and ask if the continuum hypothesis is
really
true or false. Does there really exist a set that is intermediate between
N
and (0,1)?

The continuum hypothesis is just one of the many fascinating ideas in set theory. One of the more interesting statements in set theory is called the “axiom of choice.” Let's start by looking at an easy example with finite sets. Consider the set of all U.S. citizens. They can be partitioned into fifty nonoverlapping sets that correspond to the fact that people live in fifty different states.
⁹
We may ask for a single set of citizens that has exactly one member or representative for each subset. The simplest way of forming this set is to choose the governor of each state as the representative of that state. We could also have chosen the senior senator from the state, or the oldest person in the state. We could have made many different choices. However, what if we are given a partition on an
infinite
set? Can we still choose one element of each subset? Things seem a little more complicated in the infinite case. Imagine being presented with an infinite set of pairs of shoes. (For some, this would result in an infinite amount of joy.) We may ask for one shoe from every one of the infinite pairs. This can simply be done by always choosing the left shoe in every pair. One may also choose the right shoe in every pair. However, what if we are presented with an infinite set of pairs of tube socks where each sock is identical to its mate? Can we still choose one from each pair? Which one? There is no way of describing the function. One might say no such choice is possible. We will see that assuming one can always make such a choice leads to trouble.