# Prove that the power set of an $n$-element set contains $2^n$ elements

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 numbers 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}$$. $$\square$$

Image that replaced text.

From the above explanation, I don't understand why the set that contains $$\{a\}$$ will contain $$2^{|n|}$$ elements when it should clearly be $$2^{|1|}$$.

The construction of a new set $$S$$ is the union of the old set with cardinality $$n$$ and a new element $$\{a\}$$, therefore the set that does not contain $$\{a\}$$ still has cardinality $$n$$ and the set that contains $$\{a\}$$ is just $$\{a\}$$, one element.

Can someone please elucidate?

• It is the sets that contain $a$. Sep 14, 2014 at 16:45

You misread the proof. Since set $X$ has $n$ elements, the induction hypothesis tells us that $|\mathcal{P}(X)| = 2^n$. The set $Y = X \cup \{a\}$ has $n + 1$ elements. It subsets are either subsets of $X$, of which there are $2^n$ by the induction hypothesis, or the union of a subset $Z$ of $X$ with $\{a\}$. By the induction hypothesis, there are $2^n$ subsets $Z$ of $X$. Hence, there are $2^n$ subsets of the form $Z \cup \{a\}$ of the set $Y$. Hence, $Y$ has $2^n$ subsets that do not contain $a$ and $2^n$ subsets that do contain $a$ for a total of $2^n + 2^n = 2 \cdot 2^n = 2^{n + 1}$ subsets of $Y$, which is what the author wants to show.

• Sorry, you lost me on the fourth sentence. Can you show me explicitly what is $Z$? Sep 14, 2014 at 17:00
• Oh I think I see it now, could you elaborate whether if I take the union of two sets say {A,B} U {C}, do I get {A, B, C} or {A, B, {A,C}, {B,C}}? Sep 14, 2014 at 17:11
• @ Aåkon I think it's the former. He introduced $Z$ ($2^{n}$ times) to show that $\mid \mathcal{P}(Y) \setminus \mathcal{P}(X) \mid = \mid \mathcal{P}(X)\mid$ Feb 9, 2019 at 13:02
• @N.F .Taussig: There are a confusing point in this proof. You state that $Y = X \cup \{a \}$ has as its subsets either subsets of $X$, or unions of $\{a\}$ with subsets $Z$ of $X$. But what is the proof of this assumption? Feb 25 at 18:56

Here is an another, combinatorial proof. Let $X$ be a set with $n$ elements. To form a subset of $X$, we go over each element of $X$ and exercise a choice of whether or not to include in the subset. Every sequence of choices gives a different subset.

Since for every element, there are 2 choices, for $n$ elements, there are $2 \times 2 \times ...$ $n$ times, choices.

Therefore, there are $2^n$ distinct subsets of $X$.

• this explanation was very clear to understand Jul 23, 2018 at 4:54

Suppose you've already shown that $X=\{1,2\}$ has $2^2=4$ subsets, namely ${\cal P}(X)=\{\emptyset,\{1\},\{2\},X\}$. Now you add a new element $a=3$ to get $Y=X\cup \{a\}=\{1,2,3\}$. The four subsets of $X$ are also subsets of $Y$, but you get new subsets - those which contain $a$, e.g. $\{1,3\}$. But each of these is one of the ones you already had together with the new $a$, e.g. $\{1,3\}$ is $\{1\} \cup \{3\}$.

So, the new ones are $\emptyset \cup \{3\}$, $\{1\} \cup \{3\}$, $\{2\} \cup \{3\}$, and $X \cup \{3\}$ and those are exactly as much as you already had - four of them. Which implies that ${\cal P}(Y)$ has twice as much elements (the old ones and the new ones) as ${\cal P}(X)$, so $2\times2^2=2^3=8$.

$$\begin{array}{|c|c|} \hline \text{Subsets of }X&\text{New subsets}\\ \hline \emptyset&\{3\}\\ \hline \{1\}&\{1,3\}\\ \hline \{2\}&\{2,3\}\\ \hline X&Y\\ \hline \end{array}$$

Alternative proof:

Represent a subset of $$X$$ as a binary number such that its $$k^{th}$$ bit is set if and only if the $$k^{th}$$ element is taken.

E.g., $$\{a,b,c\}\to111$$, $$\{a,c\}\to101$$, $$\{c\}\to001$$, ...

You can convince yourself that the two representations are equivalent, and that the second includes all binary numbers from $$0$$ to $$2^{|X|}-1$$.

Note that if you add an element, the subset of $$X$$ with signature $$m$$ generates two new subsets, with signatures $$2m$$ and $$2m+1$$.

I will prove the claim by induction. First suppose $$|A|=1$$. That is, $$A=\{a_1\}$$. Thus, $$P(A) =\{ \{a\}, \{ \emptyset \} \}$$. So, it can be concluded that $$|A|=2^1=2$$. My inductive hypothesis is that $$|A|=n$$ and $$|P(A)|=2^n$$. Now let's consider $$A'$$, where $$A'$$ is $$A$$ with one new element added, call it $$a_{n+1}$$. That is to say $$A'= \{a_1,a_2,a_3,\dots,a_{n+1} \}$$. When considering $$P(A')$$ two types of sets arise, those containing $$a_{n+1}$$ and those that do not. Allow $$B_i$$ to represent any particular member of $$P(A)$$. Notice that $$|P(A')|=|P(A)|+|B_k \cup\{a_{n+1}\}|$$, for all $$k\in \mathbb{N}$$ satisfying $$1\leq k\leq 2^n$$. Therefore $$|P(A')|=2^n+2^n=2\cdot 2^n=2^{n+1}$$. $$\square$$

Here is another one that uses the Binomial Theorem.

Take, for example, the set $$A = \{1, 2, 3, 4\}$$

Then, $$P(A) = \{∅, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 1\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 1\}, \{4, 1, 2\}, \{1, 2, 3, 4\}\}$$

In $$P(A)$$, see that the number of subsets with cardinality 0 is 1, there are 4 subsets with cardinality 1, 6 with cardinality 2, then 4 again with 3 and then 1 more with cardinality 4. $$\pmb{1-4-6-4-1}$$; $$16$$ total. Note that these are the coefficients of the terms when you expand the binomial theorem (binomial coefficients) with $$n=4$$.

Now we want the sum of these numbers. This is can be easily achieved by replacing $$x=y=1$$ in the binomial formula where $$n$$ is the cardinality of set A and the formula follows from there.

Why the pattern appears is very simple. Let $$n$$ be $$|A|$$. You want to fill subsets of cardinalities $$0, 1, \cdots,\ n$$. You have n elements to choose from. So to fill the first subset with cardinality 0, you use $$\binom{n}{0}$$, for the second with cardinality 1 we use $$\binom{n}{1}$$ and so on.