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 2n.

Proof: Let S1={x1} be an arbitrary set containing 1 element. Then P(A)={Ø,{x1}} and |P(A)|=2=21. Thus a set containing 1 element has 2 subsets, and the theorem holds.

Now assume that a set containing k elements has 2k subsets. Let Sk+1={x1,x2,...,xk,xk+1} be a (k+1)-set. Consider two Cases:

1) subsets containing xk+1
2) subsets not containing xk+1

By the induction hypothesis, Case 2 has 2k subsets. The total number of subsets of Sk+1 is equal to the number of subsets of Case 1 plus the number of subsets of Case 2. Consider all the subsets of Sk. Each subset of Case 1 gives a subset of Case 2 by the union of the element xk+1 to each of the subsets of Sk. Therefore, there is a one-to-one correspondence between Case 1 and Case 2. Therefore the total number of elements of Sk+1 is equal to the number of subsets of Case 1, 2k, plus the number of subsets of Case 2, 2k.

2k+2k=2k(1+1)=2k(2)=2k+1

Therefore by the Principle of Mathematical Induction, the cardinality of all subsets of A, |P(A)|, is equal to 2n for all positive integers n. Q.E.D.

Log in or register to write something here or to contact authors.