How to use the induction hypothesis in this equipotency problem?

Question

Prove by induction that $A \approx n$, then $\mathcal{P}(A) \approx2^n$

I've proved for $A\approx 1$ and i supposed that $A\approx n$ then $\mathcal{P}(A) \approx 2^n$.

But, how i can use the induction hypothesis in $\mathcal{P}(A)\approx 2^{n+1}$

Answer 1

Let $A_n$ be a set of $n$ elements and $\mathcal{P}(A)$ be the power set of $A$. For the base case, $n=1$, we hace $$A_1 = \{a_1\} \, \text{and} \, \mathcal{P}(A_1) = \{\emptyset,A_1\} $$ Thus $|\mathcal{P}(A_1) |=2 =2^n$ and the base case holds. Now suppose for $n=k$, $|\mathcal{P}(A_k)| = 2^k$.Then for $n=k+1$, $$ A_{k+1} = \{a_{k+1}\} \cup A_k$$ It follows that $$\mathcal{P}(A_{k+1}) = \mathcal{P}(A_k) \cup\{\{a_{k+1}\}\cup B, \, \forall B \in\mathcal{P}(A_{k})\}$$ We see now that $|\mathcal{P}(A_{k+1})|=2^{k+1}$ and the desired result follows.

Answer 2

OK, you add one element $a^{'}$ to a set $A$ with $n$ elements and, by induction hypothesis, with $2^n$ subsets. Now all those subsets are in the new power set. Moreover, we can create $2^n$ new subsets by adding in $a^{'}$ to all those subsets. But $2 2^n$ is $2^{n+1}$. Moreover, no other new sets can be formed - they are all obtained by either adding $a^{'}$ in or not adding it in.