**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 E_{1}, E_{2}, E_{3}, and
so on.

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

E_{1}E_{2}E_{3}E_{4}E_{5}______________________________ 1 |01 1 0 0 ... 2 | 110 0 1 ... 3 | 0 000 1 ... 4 | 0 0 111 ... 5 | 1 0 1 01... ... ... ... ... ... ... ...

(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 E_{i} 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