Size of the power set

Introduction. Let $X$ be any arbitrary set. We say a set $Y$ is a subset of $X$ (written $Y \subseteq X$ ) if every element of $Y$ is also an element of $X$ . For example, $\{ 1, 2, 3 \} \subseteq \mathbb{N}$ , every set is a subset of itself, and the empty set is the only subset of itself.

Again consider set $X$ . We define the power set of $X$ , $\mathcal{P}(X)$ , as

$\mathcal{P}(X) = \{ A ~|~ A \subseteq X \}$ .

Thus the power set of $X$ is “the set of all subsets of $X$ ”. Here are a few examples of power sets:

Let $A = \{ 1, 2, 3 \}$ . Then the power set of $A$ is $\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \}$ ;
Let $B = \{ \textrm{red},\textrm{blue} \}$ . Then the power set of $B$ is $\{ \emptyset, \{\textrm{red}\}, \{\textrm{blue}\}, \{\textrm{red},\textrm{blue}\} \}$ ;
The power set of $\emptyset$ is $\{ \emptyset \}$ . Notice that these two are different: the former is a set with no elements, while the latter is a set with a single element which happens to be the empty set.

We now pose an interesting question: given a set $X$ with $n$ elements (written $|X| = n$ ), what is the number of elements of its power set $\mathcal{P}(X)$ (written $|\mathcal{P}(X)|$ )? Peeking at concrete examples like those above, $2^n$ looks like the correct answer — even for the last one, since $2^0 = 1$ . But is it really so?

Theorem. Let $X$ denote an arbitrary set such that $|X| = n$ . Then $|\mathcal{P}(X)| = 2^n$ .

Proof. The proof is by induction on the number of elements of $X$ .

For the base case, suppose $|X| = 0$ . Clearly, $X = \emptyset$ . But the empty set is the only subset of itself, so $|\mathcal{P}(X)| = 1 = 2^0$ .

Now the induction step. Suppose $|X| = n$ ; by the induction hypothesis, we know that $|\mathcal{P}(X)| = 2^n$ . Let $Y$ be a set with $n+1$ elements, namely $Y = X \cup \{ a \}$ . There are two kinds of subsets of $Y$ : those that include $a$ and those that don’t. The first are exactly the subsets of $X$ , and there are $2^n$ of them. The latter are sets of the form $Z \cup \{ a \}$ , where $Z \in \mathcal{P}(X)$ ; since there are $2^n$ possible choices for $Z$ , there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal{P}(Y)| = 2^n + 2^n = 2^{n+1}$ . $\Box$

Like this:

Be the first to like this post.

This entry was posted on February 28, 2009 at 02:53 and is filed under Proof. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Math Proofs

Size of the power set

Like this:

Leave a Reply Cancel reply

Follow “Math Proofs”