# What is the proof that the total number of subsets of a set is $2^n$?

What is the proof that given a set of $n$ elements there are $2^n$ possible subsets (including the empty-set and the original set).

-
$2^n=(1+1)^n=\sum_{k=0}^n \binom{n}{k}$ and $\binom{n}{k}$ gives you the number of ways of choosing $k$ elements from the set with $n$ elements. –  Artem Oct 31 '13 at 2:26
cool I actually get this proof. One question: what is the step (1+1)^n actually necessary for? –  Celeritas Oct 31 '13 at 2:33
@Artem Okay, you have reduced it to an application of the binomial theorem, which is less basic and is no easier to prove. –  Trevor Wilson Oct 31 '13 at 2:34
@TrevorWilson Thanks for you opinion. –  Artem Oct 31 '13 at 2:41

Suppose you want to choose a subset. For each element, you have two choices: either you put it in your subset, or you don't; and these choices are all independent.

Remark: this works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that $2^0=1$ reflects the fact that there is only one way to pick no elements at all!

-
And where does the $2^n$ come from? This isn't really a complete proof yet. –  Trevor Wilson Oct 31 '13 at 2:36
Another way to say this is that each subset can be tagged with a binary number constructed by using $\ n \$ digits and writing "0" or "1" at each digit according to whether the $\ k^{th} \$ element is in the subset. The numbers range from $\ 000 ... 000 \$ for $\ \varnothing \$ to $\ 111 ... 111 \$ for the full set of $\ n \$ elements. So if the set has five elements, for instance, the binary numbers run from $\ 00000 \$ to $\ 11111 \$ , or 0 to 31 ; thus, $\ 2^5 \ = \ 32 \$ subsets. –  RecklessReckoner Oct 31 '13 at 2:37
Okay, I guess the argument in this answer and in the comment below it are more or less complete proofs if we define $2^n$ as the number of functions from $n$ to the set $\{0,1\}$, rather than by recursion. –  Trevor Wilson Oct 31 '13 at 2:38
@TrevorWilson Well, sure it is. $2$ choices for each element, so $\underbrace{2\cdot 2\cdot 2\cdots 2\cdot 2}_n=2^n$ possible choices in total. –  Pedro Tamaroff Oct 31 '13 at 2:38
@PedroTamaroff When a proof uses "...", recursion is usually hiding. Looking at the tags, I got the sense the OP might want something more formal. –  Trevor Wilson Oct 31 '13 at 2:39

Here is a proof by induction on $n$. This proof assumes that we have defined $2^n$ by recursion as $2^0 = 1$ and $2^{n+1} = 2^n \cdot 2$.

This is true for $n=0$ because $\emptyset$ has exactly one subset, namely $\emptyset$ itself.

Now assume that the claim is true for sets with $n$ many elements. Given a set $Y$ with $n+1$ many elements, we can write $Y = X \cup \{p\}$ where $X$ is a set with $n$ many elements and $p \notin X$. There are $2^n$ many subsets $A \subset X$, and each subset $A \subset X$ gives rise to two subsets of $Y$, namely $A \cup \{p\}$ and $A$ itself. Moreover, every subset of $Y$ arises in this manner. Therefore the number of subsets of $Y$ is equal to $2^n \cdot 2$, which in turn is equal to $2^{n+1}$.

-

We must show that $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$$ is the number of subsets of an $n$-element set $S$ where $n\geq0$.

Every subset of $S$ is a $k$-subset of $S$ where $k=0,1,2,...,n$. We know that ${n\choose k}$ equals the number of $k$-subsets of S. Thus by the Addition Principle $${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}$$ equals the number of subsets to the set $S$. We can count the same thing by observing that each element of the set $S$ has two choices, either they are in a subset or they are not in a subset. Let $S=\{x_1,x_2,x_3,...,x_n\}$. So, $x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,..., $x_n$ is either in a subset or it is not in a subset. Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$. Hence ${n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n$.

Another approach is to consider the Binomial Theorem $$(x+y)^n=\sum_{k=0}^n {n\choose k}x^{n-k}y^k.$$ Letting $x=1$ and $y=1$ we obtain$$2^n=\sum_{k=0}^n{n\choose k}.$$

-
It seems like the proof is entirely contained in the part saying "$x_1$ is either in a subset or it is not in a subset, $x_2$ is either in a subset or it is not in a subset,.... Thus by the Multiplication Principle there are $2^n$ ways we can form a subset of the set $S$." The other stuff is of course correct and generally useful, but it doesn't seem to fit into the proof of what the OP is asking for a proof of. –  Trevor Wilson Oct 31 '13 at 3:10
I agree with you. I just wanted to present Celeritas a thorough combinatorial proof to his question. It is to help him understand the problem better. He can only benefit from reading all the extra stuff. –  Ross Belgram Oct 31 '13 at 3:21
I agree, especially if he/she is taking a combinatorics class. It's just that the extra stuff is only necessary if you want to prove that the two things (1) the number of subsets of an $n$ element set and (2) $2^n$ are, as well as being equal to one another, both equal to a third thing (3) $\sum_{k=0}^n \binom{n}{k}$. So I was scratching my head over the logical structure of the proof until I realized that you wanted to prove this extra thing also. –  Trevor Wilson Oct 31 '13 at 3:26

Here is proof by binary numbers. A set of up to N items can be represented as a vector of binary digits. When a digit is 1, it indicates that the corresponding item is present. 0 means that it is absent.

In fact, this representation is used in computer programming as a way of representing sets which has good worst-case memory efficiency, as well as other attributes such as simplicity of implementation.

So for instance a set of 32 items can be represented as a string of 32 1's. And then we can represent subsets of these items, by flipping some of these 1's to 0's in various combinations.

All possible subsets are therefore, simply, all possible 32 bit numbers, and there are $2^{32}$ such numbers.

In other words, the count of subsets is related to the fact that set membership is a binary proposition: something is or is not an element of a set. Yes or no, true or false, one or zero.

-

Here's a combinatoral proof $$\sum_{k=0}^n{n \choose k}=2^n$$ These both count the number subsets in an $n$ element set. The right hand side counts them directly (related to Marie's answer) and the left hand side counts the number of $k$-element subsets and then sums over $k$. This equation can also be verified by the binomial theorem with $x=y=1$.

-

Let us take the following cases :

(I) Let a set be $\{a\}$ therefore, its subsets are : $\{a\}$ ${\phi}$ . Therefore the number of subsets are $2^1$

(II) Let another set be $\{a,b\}$, its subsets are : $\{a\},\{b\},\{a,b\}, {\phi}$ Therefore the number of subsets are $2^2$

(II) Let another set be $\{a,b,c\}$ , its subsets are : $\{a\},\{b\},\{c\},\{a,b,c\},\{a,b\},\{a,c\},\{c,a\}, {\phi}$. Therefore the number of subsets are $2^3$

$\therefore$ (I), (II) & (III) $\Rightarrow$ If there are $n$ sets then the number of subsets are $2^n$

-
This is a useful illustration, but I don't think that checking three cases is enough to be sure that something holds for all natural numbers $n$. –  Trevor Wilson Oct 31 '13 at 2:55
This is more on route to prove by induction. As Trevor Wilson said, because a pattern follows for $n=1,2,3$ does not imply that it holds for all $n$ –  MITjanitor Oct 31 '13 at 3:04

If $S$ is a finite set with $|S| = n$ elements, then the number of subsets of $S$ is $|\mathcal{P}(S)| = 2^n$. This fact, which is the motivation for the notation $2^S$, may be demonstrated as follows,

We write any subset of $S$ in the format $\{x_1, x_2, \ldots, x_n\}$ where $x_i , 1 \le i \le n$, can take the value of $0$ or $1$. If $x_i = 1$, the $i$-th element of $S$ is in the subset while the $i$-th element is not in the subset otherwise. Clearly the number of distinct subsets that can be constructed this way is $2^n$.

-