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

[16-Aug-1996]