# Proof of the formula for the number of subsets of an n-element set

Given a set $A = \{1,2,...,n\}$, the number of subsets of this set can be given by the cardinality of the powerset of A: $$|\mathscr P(A)| = 2^n$$ This is fairly standard and I'm happy with the concept. I am curious, however, as to how one would go about constructing a proof for this, as I've only been presented with a half proof that, to me, doesn't seem to hold up as a rigorous proof. I'll put it here anyway, though.

Let $A = \{a_1,a_2,...,a_n\}$, then we can describe any subset, $S$, of $A$ by answering $n$ questions about it:

• is $a_1 \in S$ ? - Yes/No
• is $a_2 \in S$ ? - Yes/No

.

.

• is $a_n \in S$ ? - Yes/No

Each answer specifies a subset and so there are $2^n$ possible answers.

$\therefore |\mathscr P(A)| = 2^n$

This is exactly what I have written in my lecture notes and not only does it not seem to constitute a proper proof, it doens't seem to entirely make sense to me. For example, when it says that each answer specifies a subset, what does it actually mean? Sure we can have each individual element of $A$ as a subset but then wouldn't we start having subsets that have a cardinality of more than 1?

i.e $\mathscr P(A) = \{\{1\},....,\{n\},\{1,2\},...\}$

and when we get to $\{1,2\}$ we would have to start answering 2 questions about weather or not $1 \in S$ and $2 \in S$.

If someone could clarify what this mess of a proof is actually trying to say and possibly point me in the right direction of a rigorous proof I would be very grateful. Thanks

$P(A)$ is the cardinality of $Map(A,\{0,1\})$ the sets of maps $A\rightarrow \{0,1\}$ which is $2^n$.

Each map $f:A\rightarrow \{0,1\}$ is the characteristic function of a unique subset of $A$.

To compute the cardinality of $Map(A,\{0,1\})$ remark that if $A=\{1,...,n\}$, you have 2 choices to define the image of $i\in\{1,...,n\}$ this gives you $2^n$ choices.

Go by induction, if you like. There is a bijection between $\mathcal{P}\{ 1, 2, \dots, n \}$ and $\mathcal{P}(\{1, 2, \dots, n-1 \}) \times \{0, 1\}$, given by $$\phi: A \mapsto \langle A \setminus \{ n \}, 1[n \in A] \rangle$$ where $1[n \in A]$ is the indicator function which takes the value $1$ if $n \in A$, and $0$ otherwise.

This is clearly bijective: indeed, it has inverse $(X, 1) \mapsto X \cup \{n\}$, and $(X, 0) \mapsto X$.

Now, what is the cardinality of $\{1, 2, \dots, n-1 \} \times \{0, 1\}$? It's the cardinality of $\{1, 2, \dots, n-1\}$ times the cardinality of $\{0,1\}$, which is inductively $2^{n-1} \times 2 = 2^n$.

1. How do you specify a subset of $A$?

A common way is to write down all the elements of the subset. This is the same as to answer the $n$ questions you wrote.

Suppose $A_1,A_2\subset A$. It is easy to see that $A_1=A_2$ if and only if, to each question, you get the same answers for $A_1$ and $A_2$.

1. How many answers you can get?

For each question, there are two different answers. Hence, there are $2^n$ different answers. Therefore, there are $2^n$ different subsets of $A$.

Err... You ALWAYS ask ALL $n$ questions, even for subsets with only one element! In those cases, one answer is yes and the rest are no.

Trying to explain this in English obscures what's going on. Logically, the proof is this:

FIRST, consider the set of all ordered $n$-tuples of 0 and 1. For example, for $n$ = 3, these are 000, 001, 010, 011, .... This set is $\{0,1\} \times \cdots \times\{0,1\}$ (Cartesian product), which shows the cardinality is $2^n$. Then, arrange the elements of $A$ in a sequence: $\{a_1, \dots, a_n\}$ (prove by induction that such an ordering always exists). Then establish a bijection between the set of ordered $n$-tuples of 0 and 1 to $\cal P (A).$ Specifically, to every given $n$-tuple, associate the subset of $\{a_k\}$ where the $k^{\text th}$ element in the $n$-tuple is 1. Show this is indeed a bijection, it's easy. This bijection is described in words by the yes/no questions in your formulation.

For a completely different proof (not related to yes/no question): Induction by $n$. Fix an element of $A$, call it $a_n$. $\cal P(A)$ is the disjoint union of two families of subsets: Those that contain $a_n$ and those that don't. BOTH families are in obvious bijection with $\cal P (A \setminus \{a_n\})$ (one of them IS this set of subsets) so by induction each of the two families has cardinality $2^{n-1}.$ Done.

I prefer the first proof; I always prefer a direct proof when one exists, and use induction when there really is no other way (which is still often enough).

Another proof:

1. There is only one zero-set : $\binom {n}{0}$

2. How many different sets, I could make by $1$ element : $\binom{n}{1}$

3. From two elements : $\binom{n}{2}$

So, we got : $\sum_{i = 0}^{n}{\binom{n}{i}} = 2^{n}$, that's easy to prove by Pascal triangle!

• @Joanpemo yes, thanks a lot! – openspace Apr 16 '16 at 11:53
• Last equality: also by the binomial theorem (consider $(1+1)^n$). Also, why start with 1. subsets with 1 element, and not with 0. subsets with 0 elements? – mathguy Apr 16 '16 at 11:57
• @mathguy yes, but when I was young, I proved it by Pascal triangle, it was so easy, so now I recomend it always I forgot about writing about zero-set. – openspace Apr 16 '16 at 12:00

Let $a_n$ denote the number of subsets of the $n$-element set $\{1,2,\ldots,n\}$.

Clearly $a_0 = 1$, since only the empty set occurs.

Moreover $a_{n+1} = 2a_n$. For among the subsets of $\{1,2,\ldots,n+1\}$ we can distinguish two types: those which contain $n+1$ and those which dont. Those of each type are in $1-1$ correspondence with subsets of $\{1,2,\ldots,n\}$, hence the recursion.

So the sequence $(a_n)_{n=0}^{\infty}$ is defined recursively by

$$a_0 = 1, \:\:\ a_{n+1}=f(a_n), \ \text{where}\:\ f(x)=2x$$

From this it immediately follows that $a_n = 2^n$