The total number of subsets is $2^n$ for $n$ elements

Question

In my probability book, it says that to count the total number of subsets of n elements is a process of $n$ stages with binary choice of either adding this element to the subset or not to add it. Therefore, the total number is $$2^n$$

But, for instance, we have 3 elements, according to this formula, there are 2 to the power of 3 elements, namely 8, which are $${\emptyset},A,B,C, AB, AC, BC, ABC$$

However, I have a hard time of imagining the process or N stages binary choice that form this many subsets. Can anyone explain/help me to understand it? I mean, ABC, if we are making the choice of A, put it in or do not put it in, exactly which subset are we choosing to put in or not? Thank you.

Answer 1

• "Include A?" is stage 1
• "Include B?" is stage 2
• "Include C?" is stage 3.

Answer 2

Label your $n$ elements so that $X=\{x_{1},...,x_{n}\}$. We're going to form a one-to-one correspondence between the subsets of $X$ and the set of length-$n$ binary strings as follows. Given a binary string $$a_{1}\cdots a_{n}$$ imagine that $a_{i}=1$ means "include $x_{i}$ in this subset" and $a_{i}=0$ means "exclude $x_{i}$ in this subset". For example, if $n=4$ then the subset $S=\{x_{1},x_{3}\}$ would be represented as $1010$.

There are exactly $2^{n}$ possible strings, since each $a_{i}$ has two possible values, and there are $n$ of them. And each string corresponds to one and only one subset of $X$. Therefore there are $2^{n}$ subsets.

Answer 3

Write out all the binary numbers with $3$ digits. Each digit represents one element ($0$ means exclude, $1$ means include): $$ \begin{array}{|c|c|} \text{decimal}&\text{binary}&\text{subset}\\\hline 0&000&\{\}\\ 1&001&\{C\}\\ 2&010&\{B\}\\ 3&011&\{B,C\}\\ 4&100&\{A\}\\ 5&101&\{A,C\}\\ 6&110&\{A,B\}\\ 7&111&\{A,B,C\}\\ \end{array} $$ This is easily extendible to an $n$ element set with $n$ digit binary numbers.

Answer 4

I think, more directly, what the book is saying can be stated as:

Choosing a subset $U$ of a set $S$ is the same as, for each element $x\in S$, choosing whether $x$ is in $U$ or not.

In particular, there is, at any time, only one set we're considering. So, if $S=\{A,B,C\}$ and we want to choose a subset $U$, we could make the following three choices: $$A\in U$$ $$B\in U$$ $$C\in U$$ And we would get $U=\{A,B,C\}$. So, we've constructed a subset by making three binary choices. We could try this process again to make a different subset; for instance, we could decide instead $$A\not\in U$$ $$B\not\in U$$ $$C\in U$$ And then get $U=\{C\}$. So, we've made a different set of choices and got a different set. So, for each subset, we have to make three choices.

Answer 5

The set of subsets of $X$ can be seen as the set of all functions from $X$ to $\{0,1\}$, denoted $\{0,1\}^X$.

For each such function, consider the subset of $X$ consisting of all $x\in X$ such that $f(x)=1$.

This, it turns out, is a $1-1$correspondence.

As a result, the order of the power set is $\mid P(X)\mid=\mid \{0,1\}^X\mid=\mid\{0,1\}\mid^{\mid X\mid}=2^n$.

Answer 6

Proof by induction (on number of elements in the set):

For $n = 0$, there is exactly $2^0=1$ subset of a set with 0 elements, namely the empty set itself.

Assuming that any set $U_n$ with $n$ elements has $2^n$ subset, consider a set $U_{n+1}=U_n \cup \{x\}$ (where $x \notin U_n$). Which subsets of $U_{n+1}$ exists?

• The subsets which do not include $x$ are exactly the subsets of $U_n$ (there are $2^n$ such subsets)
• Any other subset includes $x$, so it is of the form $A \cup \{x\}$, where $A$ is a subset of $U_n$ (because all elements in $U_{n+1}$ except $x$ are also elements of $U_n$), and it's clear that such subset exists (and is unique) for each $A \subset U_n$. So, the number of $U_{n+1}$ subsets which include $x$ is also $2^n$.

So, the total count of $U_{n+1}$ subsets is $2^n+2^n=2^{n+1}$. The proof is complete.