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.