[Overview] [Previous] [Next]

Nondenumerable Powersets

Theorem. The powerset of an infinite (denumerable) set is not denumerable.

Proof. The proof is by diagonalization.

Put the elements of the infinite set into a one-to-one correspondence with the natural numbers. (By hypothesis, the set is denumerable, so this step must be possible.) Then we can refer to the elements of the set as E1, E2, E3, and so on.

The elements of the powerset will be subsets of {E1, E2, E3, ...}. Assume we can put these subsets into a one-to-one correspondence with the natural numbers, as follows:

         E1   E2   E3   E4   E5
       ______________________________
   1  |   0    1    1    0    0   ...
   2  |   1    1    0    0    1   ...
   3  |   0    0    0    0    1   ...
   4  |   0    0    1    1    1   ...
   5  |   1    0    1    0    1   ...
  ...    ...  ...  ...  ...  ...  ...

(In the table, a 1 indicates that the element is present in the subset, and a 0 indicates that it is absent.) Now construct a new subset, as follows: For each natural number i, element Ei belongs to this new subset if and only if it doesn't belong to subset i.

Since this new subset differs from every subset in the correspondence by the presence or absence of at least one element, the correspondence is faulty. But since the only assumption we made about the correspondence is that it exists, no such correspondence can exist, and the powerset is not denumerable. Q.E.D.


Copyright 1996 by David Matuszek
Last modified Mar 31, 1996