Definition:

Cardinality of a

set A, denoted |A|, is the number of elements in A.

Definition: The

Power Set of A, denoted P(A), is the set of all possible

subsets of A.

Example: A={1,2,3} then P(A)={Ø,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. Also, |A|=3 and |P(A)|=8.

Theorem: Let |A|=n for some positive integer n. The cardinality of all subsets of A, |P(A)|, is equal to 2

^{n}.

Proof: Let S

_{1}={x

_{1}} be an

arbitrary set containing 1 element. Then P(A)={Ø,{x

_{1}}} and |P(A)|=2=2

^{1}. Thus a set containing 1 element has 2 subsets, and the theorem holds.

Now assume that a set containing k elements has 2

^{k} subsets. Let S

_{k+1}={x

_{1},x

_{2},...,x

_{k},x

_{k+1}} be a (k+1)-set. Consider two

Cases:

1) subsets containing x

_{k+1}
2) subsets not containing x

_{k+1}
By the

induction hypothesis, Case 2 has 2

^{k} subsets. The total number of subsets of S

_{k+1} is equal to the number of subsets of Case 1 plus the number of subsets of Case 2. Consider all the subsets of S

_{k}. Each subset of Case 1 gives a subset of Case 2 by the

union of the element x

_{k+1} to each of the subsets of S

_{k}. Therefore, there is a

one-to-one correspondence between Case 1 and Case 2. Therefore the total number of elements of S

_{k+1} is equal to the number of subsets of Case 1, 2

^{k}, plus the number of subsets of Case 2, 2

^{k}.

2

^{k}+2

^{k}=2

^{k}(1+1)=2

^{k}(2)=2

^{k+1}
Therefore by the

Principle of Mathematical Induction, the cardinality of all subsets of A, |P(A)|, is equal to 2

^{n} for all positive integers n.

Q.E.D.