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]