Outer Limits of Reason (17 page)

This is also shown with a proof by contradiction:

There is a correspondence between
N
and
(
N
) ⇒ contradiction.

The contradiction is derived by describing a subset of natural numbers—that is, an element of
(N
)—that is not in the proposed correspondence. Since we assumed the correspondence pairs off every subset of natural numbers, we have a contradiction.

Informally the proof proceeds by describing a subset of natural numbers as

This subset of natural numbers is not in the given correspondence.

Or, more precisely,

This subset of natural numbers is different from every subset of natural numbers given in the correspondence.

Formally, this is again shown with a diagonalization proof. Assume that there is a correspondence between
N
and
(
N
)—that is, there is a way of pairing every natural number
n
and a subset of
N
. Rather than listing the elements of the subset, we will state yes or no depending if an element is in the subset. A description of a correspondence can be illustrated as in
figure 4.7
.

Let's look at a few of the subsets. The subset that corresponds to number 1 contains 0
,
does not contain 1, contains 2, contains 5, and so on. So this subset is

{0, 2, 5, . . .}

The subset that corresponds to number
7
is

{1, 5, 7, 8, . . .}.

This correspondence cannot contain all subsets of
N
. By looking at the diagonal, we can find a subset not on the list. Let's look at the opposite of what is on the diagonal, as in
figure 4.8
.

Subset
D
will

• not contain 0 because the subset that corresponds to number 0 contains 0;

• contain 1 because the subset that corresponds to number 1 does not contain 1;

• not contain 2 because the subset that corresponds to number 2 contains 2;

• not contain 3 because the subset that corresponds to number 3 contains 3;

• 

• contain
d
₀
if and only if the subset that corresponds to number
d
₀
does not contain
d
₀
;

• 

We are really describing the subset of natural numbers:

D =
{
d
in
N
: the subset that corresponds to
d
does not contain
d
}.

The claim is that
D
does not correspond to any element of the natural number. If one were to say that subset
D
corresponds to number
d
₀
, then see if the number
d
₀
is in
D
.

d
₀
is in
D
if and only if
d
₀
is not in the subset that corresponds to
d
₀
.

That is,

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

This is a contradiction. We conclude that the subset
D
is different from the subset corresponding to number
d
₀
. In fact,
D
is different from any subset in the proposed correspondence. Hence, our correspondence is missing at least one subset.

The natural numbers did not really play a major role in the last proof. We can generalize this proof and show that for any set,
S
, the powerset of
S
cannot be put into correspondence with
S
. That is, there are more subsets than elements of a set. This coincides nicely with our theme about the limitations of self-reference. The elements of the set
S
cannot “correspond,” “describe,” or “handle” all the membership properties of the set
S.

The short proof goes as follows: imagine (falsely) that there is a correspondence between
S
and
(
S
). Now consider the set

D =
{
d
in
S
: the subset of
S
that corresponds to
d
does not contain
d
}.

D
is a subset of
S
and hence an element in
(
S
), but
D
does not correspond to any element of
S.
In effect,
D
says