2 - Diagonalization

Summary

In the preceding chapter we introduced the distinction between enumerable and nonenumerable sets, and gave many examples of enumerable sets. In this short chapter we give examples of nonenumerable sets. We first prove the existence of such sets, and then look a little more closely at the method, called diagonalization, used in this proof.

Not all sets are enumerable: some are too big. For example, consider the set of all sets of positive integers. This set (call it P^*) contains, as a member, each finite and each infinite set of positive integers: the empty set Ø, the set P of all positive integers, and every set between these two extremes. Then we have the following celebrated result.

Theorem (Cantor's Theorem). The set of all sets of positive integers is not enumerable.

Proof: We give a method that can be applied to any list L of sets of positive integers in order to discover a set Δ(L) of positive integers which is not named in the list. If you then try to repair the defect by adding Δ(L) to the list as a new first member, the same method, applied to the augmented list L^* will yield a different set Δ(L^*) that is likewise not on the augmented list.

The method is this. Confronted with any infinite list L

of sets of positive integers, we define a set Δ(L) as follows:

(^*) For each positive integer n, n is in Δ(L) if and only if n is not in S_n.