Exercise 1.8

Proof. We show this by induction on the size of the set. For the base case, start with the empty set in which $n=0$. Clearly the only subset of $\text{∅}$ is the trivial subset $\text{∅}$ itself so that $\varnothing =\left\{\text{∅}\right\}$. This has $1=2^0=2^n$ element obviously, which shows the base case. Now suppose that the power set of any set with $n$ elements has $2^n$ elements. Let $A$ be a set with $n+1$ elements, noting that this is nonempty since $n+1\ge 1$ since $n\ge 0$. Hence there is an $x\in A$. For any subset $B\subset A$, either $x\notin B$ or $x\in B$. In the first case $B$ is a subset of $A-\left\{x\right\}$ and in the latter $B=\left\{x\right\}\cup C$ for some $C\subset A-\left\{x\right\}$. Therefore $A$ has twice the number of elements of $A-\left\{x\right\}$, one half being just the elements of $A-\left\{x\right\}$ and the other being those elements with $x$ added in. But $A-\left\{x\right\}$ has $n$ elements since $A$ has $n+1$, and hence $A-\left\{x\right\}$ has $2^n$ elements by the induction hypothesis. Thus $A$ has $2\cdot 2^n=2^{n+1}$ elements, which completes the induction. □