Power Set
2026-02-28 13:56 Diff
https://brightchamps.com/en-us/math/algebra/power-set

The cardinality of a power set represents all possible subsets, including the empty set and the set itself. Take, for example, the set C = x, y, z, w. This set contains 4 elements, so the cardinality of c is 4. The cardinality of its power set is 24 = 16. So the power set of C has 16 subsets.

Power Set Proof

To show that if a set A contains n elements, then its power P(A) has 2n elements. In other words, the cardinality of a finite set A with ‘n’ elements is |P(A)| = 2n.We follow the pattern of mathematical induction for the proof of the power set.

Let's consider the case of an empty set.

Case 1: A set with no elements, n = 0 

Let A =  (empty set)


The only subset of the empty set is itself, so P() = .


Since there is only 1 element in the set, the cardinality of the set will be 2n = 21 = 1.

Case 2: We now assume that the rule holds for a set with n elements such that a set 2n has subsets.
Let's call this set X, now suppose

X = nP(X) = 2n

Now, let's create a new set Y by adding one new element, say an+1, to set X:

Y = X U an+1

So the number of elements in Y is n + 1.

There are 2 kinds of subsets in Y: one having the new element an = 1 and the other without it.

So in total: P(Y) = 2n(without an+1) + 2n(with an+1) =22n = 2n+1  

This proves that if the formula holds for n, it also holds for n + 1.

Let us apply this proof using an example,

Let X=a, b, c 

Let Y=a, b, c, d

Here,

X = 3, so the number of subsets of X is 23 = 8

Y = 4, and we’ll prove that the number of subsets of Y is 24 = 16.

Subsets of X = {}, a,b,c,a,b,a,cb,ca,b,c

So, X has a total of 8 subsets.

Subsets of Y = {},a,b,c,a,b,a,c,b,c,a,b,c

These are 8 subsets that do not include d.

Now for subsets of Y with d = {d},a,d,b,d,c,d,a,b,d,a,c,d,b,c,d,a,b,c,d

There are 8 more subsets of Y when d is added.

Total subsets of Y = 16.

Here, 4 is the extra element in set Y.

This example confirms that if a set with n elements has 2n subsets, then adding one more element doubles the number of subsets to 2n+1.