 ## The power set of a set is larger than the set itself

The power set P of a set S is the set of all subsets of S. If S is finite and has N elements then P has 2^N elements. Obviously, for finite N,

2^N > N.

Remarkably, a similar statement holds for infinite sets !

What do we mean by that? As described elsewhere P is larger than S if S is equivalent to a subset of P but P is not equivalent to a subset of S. We can pair every element x of S with the subset {x} of S, and so clearly S is equivalent to a subset of P.

To show that P is not equivalent to S we suppose that it is and obtain a contradiction. To this end we construct a subset T of S that cannot be paired with any element of S. Let X(x) denote the subset of S paired with x. For every x there are two possibilities: x is an element of X(x), or it is not. Let T be the set of all x in S such that X(x) does not contain x. By its definition, T cannot be paired with any element of T, and it cannot be paired with any element of S not contained in T. In other words, it is not paired with any element of S.

[16-Aug-1996]