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*,

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*.

Fine print, your comments, more links, Peter Alfeld, PA1UM

[16-Aug-1996]