##
The size of a finite power set

** Let ***S* be a finite set with *N* elements.
Then the powerset of *S* (that is the set of all subsets
of *S* ) contains 2^N elements. In other words, *S
* has 2^N subsets. This statement can be proved by
induction. It's true for *N=0,1,2,3* as can be shown by
examination.
For the induction step suppose that the statement is true for a
set with *N-1* elements, and let *S* be a set with
*N* elements. Remove on element *x* from *S
* to obtain a set *T* with *N-1* elements.
There are two types of subsets of *S*: those that
contain *x* and those that do not contain *x*.
The latter are subsets of *T*, of which there are 2^ *
N-1*. Every subset * P* of *S* that does
contain *x* can be obtained from a subset *Q* of
*T* by adding *x*. The set *Q* is simply
the set *P* with *x* removed. Clearly there is a
unique and distinct set *Q* for each set *P* and
every subset *Q* of *T* gives rise to a unique and
distinct subset *P* of *S*. There are thus also
2^ *(N-1)* subsets of *S* that contain *x*,
for a total of
2^ *(N-1)* + 2^ *(N-1)* = 2^ *N*
subsets of *S*.

** Note:** The notation *2^N* means 2 to the power
*N*, i.e., the product of *N* factors all of
which equal 2. *2^0* is defined to be 1. You can see
details.

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

[16-Aug-1996]