Why is finding all subsets of a set (power set) an exponential problem?

Question

I know it's function of $2^n$ where $n$ is the number of elements in the original set. But what is so doubling (100% growth) about finding all subset of a set?

Usually for $2^n$ function we can represent it as a binary tree but I can't work my way to understand why it's exponential in this case. It's a property but I can't link it to usual methods of understanding $2^n$.

Answer 1

You can represent the process of identifying all subsets of $\{1,\ldots,n\}$ as a binary tree. Here’s a rough sketch for $n=3$:

At the first stage we ask whether $1$ is in the subset; at the second whether $2$ is in the subset; and so on. Since the question always has $2$ possible answers, each level of the tree has twice as many nodes as the previous level, and after $n$ questions we have

$$1\cdot\underbrace{2\cdot 2\cdot\ldots\cdot 2}_{n\text{ doublings}}=2^n$$

nodes. Each subset of $\{1,\ldots,n\}$ is completely determined by the answers to these $n$ questions, and each string of yes/no answers completely determines a subset of $\{1,\ldots,n\}$, so at the last level there is exactly one node for each subset of $\{1,\ldots,n\}$. Thus, $\{1,\ldots,n\}$ must have $2^n$ subsets.

Answer 2

What follows is something I wrote a while back for a problem that appears in the beginning of Munkres' famed Topology text. I'm posting a picture because I'm too lazy to type it all out verbatim, but I imagine it may address what you are referencing.

Note: Begin at "Inductive Argument 1" for the part that explicitly addresses your question.

---

Answer 3

It is sufficient that given any subset of $\{0,...,n-2\}$ (with $n-1$ elements), there are two ways to extend it to a subset of $\{0,....,n-1\}$ (with $n$ elements). But the extension either includes or excludes $n-1$, so we are done.

Answer 4

Let $I_n = \{1, \dots, n\}$. The power set $P(I_n)$ is the disjoint union of $\{X\subset I_n:\, n\not\in X\}$ and $\{X\subset I_n:\, n\in X\}$. The maps $\alpha \to \alpha$ and $\alpha \to \alpha \cap I_{n-1}$ are bijections from these respective sets onto $P(I_{n-1})$, so $\#P(I_n) = \#2P(I_{n-1})$. The result follows.