# Prove; Powerset Cardinality is $2^n$ - I have trouble understanding the prove.

I have trouble to understand the Induction step of the following prove.

Can someone explain to me what happens in the Induction step 3. and 4.?

I don't really get the idea which is used, or it is simply not understandable enough written for me.

Prove source: https://proofwiki.org/wiki/Cardinality_of_Power_Set

## Prove:

For all $n \in \mathbb{N}$, let $P(n)$ be the proposition: $$|S| = n \implies |\mathcal{P}(S)| = 2^n$$ where $\mathcal{P}(S)$ is the powerset of $S$

Basis for the Induction:

1. It holds $S = \emptyset \Longleftrightarrow |S| = 0$.
2. Then $\mathcal{P}(S) = \{\emptyset\}$, such that $|\mathcal{P}(S)| = 1 = 2^0$.
3. From (1.) and (2.) it follows that proposition $P(0)$ holds.
Induction Hypothesis:

We need to show that, if $P(k)$ is true, where $k \geq 2$, then it logically follows that $P(k+1)$ is true. So if this is our Induction Hypothesis: $$|S| = k \implies |\mathcal{P}(S)| = 2^k$$ We need to show that: $$|S| = k+1 \implies |\mathcal{P}(S)| = 2^{k+1}$$

Induction Step:

1. Let $|S| = k+1$ and let $x \in S$.
2. Consider the sets $S' = S \backslash \{x\}$, where $x$ is some element of $S$. We see that $|S'| = k$
3. We now adjoin $x$ to all the subsets of $S'$. Counting the subsets of $S$, we have: all the subsets of $S'$ and all the subsets of $S'$ with $x$ adjoined to them.
4. From the Induction Hypothesis, there are $2^k$ subsets of $S'$. Adding $x$ to each of these, does not change their number, so there are another $2^k$ subsets of $S$, consisting of all the subsets $S'$ with $x$ adjoined to them.
5. In total that makes $2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$ subsets of $S$. So $P(k) \implies P(k+1)$ and the result follows by the principle of mathematical induction.
6. Therefore: $\forall n \in \mathbb{N} : |S| = n \implies |\mathcal{P}(S)| = 2^n$
• What is the problem ? There are those sets with $x$ and those without $x$. – Rene Schipperus Oct 22 '17 at 13:56
• Hm I see, it was really confusing to me, that they adjoin $x$ to $S'$ and then talk about counting the subsets in $S'$ and $S'$ with $x$ adjoined. Maybe they should use different names these two sets, then it would be clearer. – user419869 Oct 22 '17 at 14:21

I'll illustrate with an example. Let's say we have a four element set $S = \lbrace 1, 2, 3, 4 \rbrace$. We know that, given any three element set, it has $2^3 = 8$ subsets.
Let's take out our $x$ from $S$ to form a three element set $S'$. I'm going to choose $x = 2$, for no particular reason, so $S' = \lbrace 1, 3, 4 \rbrace$. Under the induction hypothesis, we assume $S'$ has $8$ subsets, which are the following: $$\lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 3, 4 \rbrace, \lbrace 1, 4\rbrace, \lbrace 1, 3, 4 \rbrace.$$ Note that the above list are all subsets of $S$; the fact that none of them contain $x = 2$ doesn't change this. In fact these are all the sets we can form without choosing $x = 2$. We can get the rest of the sets by adding in $x = 2$ into each of the sets, to get another $8$ subsets: $$\lbrace 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 2, 4 \rbrace, \lbrace 1, 2, 3 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 1, 2, 4\rbrace, \lbrace 1, 2, 3, 4 \rbrace.$$ Try to convince yourself that the two collections of subsets form all subsets of $S'$. Every subset of $S$ that doesn't contain $2$ corresponds uniquely with a subset of $S$ that does contain $2$. We know there are $2^3$ of the former, and due to this relationship, there must also be $2^3$ of the latter. So, in total, we have $2^3 + 2^3 = 2 \cdot 2^3 = 2^4$ subsets.