86
$\begingroup$

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).

$\endgroup$
1
  • 3
    $\begingroup$ To form a subset, you must decide, for each element of the set, whether or not it will belong to the subset. There are $2$ ways to decide what to do with the first element of the set, $2$ ways to decide what to do with the second element, etc. we will have $2 \cdot 2 \cdot .... \cdot 2 = 2^n$ $\endgroup$ Dec 3, 2021 at 23:35

9 Answers 9

95
$\begingroup$

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!

$\endgroup$
7
  • 31
    $\begingroup$ 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. $\endgroup$ Oct 31, 2013 at 2:37
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 31, 2013 at 2:38
  • 6
    $\begingroup$ @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. $\endgroup$
    – Pedro
    Oct 31, 2013 at 2:38
  • 2
    $\begingroup$ @PedroTamaroff When a proof uses "...", recursion is usually hiding. Looking at the tags, I got the sense the OP might want something more formal. $\endgroup$ Oct 31, 2013 at 2:39
  • 1
    $\begingroup$ @RecklessReckoner Yes, and I should not have jumped to criticize this answer without asking the OP which definition of $2^n$ he or she was using. $\endgroup$ Oct 31, 2013 at 2:41
35
$\begingroup$

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}$.

$\endgroup$
0
26
$\begingroup$

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}.$$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Oct 31, 2013 at 3:10
  • 6
    $\begingroup$ 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. $\endgroup$
    – 1233dfv
    Oct 31, 2013 at 3:21
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 31, 2013 at 3:26
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
1
$\begingroup$

To write out some details of the discussion under this answer. Consider the two element set $\{0,1\}$ where you think of $1$ as meaning in the subset and $0$ as meaning not in the subset. In this way any function $f\colon S \to \{0,1\}$ defines a subset of $S$, where $s$ is in that subset if and only if $f(s)=1$. So then our question is how many such functions are there? For each of the $n$ elements of $S$ there are two choices for what $f(n)$ can be, so making these $n$ choices independently, there are $2^n$ options.

$\endgroup$
1
$\begingroup$

\begin{align} \sum_{k=0}^n{n \choose k}=2^n \end{align} can be solved using proof by induction.

for $n=1$; it is true (put n=1);

for $n=k$; assume to be true. \begin{align} \sum_{k=0}^n{n \choose k}=2^n \end{align} for $k=n+1$; \begin{align} \sum_{k=0}^{n+1}{n+1 \choose k}=2^{n+1}\end{align} \begin{align} {n+1 \choose k}={n \choose k}+{n \choose k-1} \end{align}

substituting this equation leads to the final result.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

Let us consider the following cases:

  1. Let a set be $\{a\}$, then its subsets are: $\{a\}, {\emptyset}$ . Therefore the number of subsets is $2^1$

  2. Let another set be $\{a,b\}$, then its subsets are: $\{a\},\{b\},\{a,b\}, {\emptyset}$ Therefore the number of subsets is $2^2$

  3. Let another set be $\{a,b,c\}$, then its subsets are: $\{a\},\{b\},\{c\},\{a,b,c\},\{a,b\},\{b,c\},\{a,c\}, {\emptyset}$. Therefore, the number of subsets is $2^3$

$\therefore$ (1), (2) & (3) $\Rightarrow $ If there are $n$ sets, then the number of subsets is $2^n$

$\endgroup$
3
  • 9
    $\begingroup$ 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$. $\endgroup$ Oct 31, 2013 at 2:55
  • 2
    $\begingroup$ 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$ $\endgroup$
    – MITjanitor
    Oct 31, 2013 at 3:04
  • $\begingroup$ Related: mathoverflow.net/questions/15444/… $\endgroup$ Jun 23, 2020 at 15:00

Not the answer you're looking for? Browse other questions tagged .