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:
    
*
        
* It holds $ S = \emptyset \Longleftrightarrow |S| = 0 $.
        
* Then  $\mathcal{P}(S) = \{\emptyset\}$, such that $|\mathcal{P}(S)| = 1 = 2^0$.
        
* 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:


*
 
* Let $|S| = k+1$ and let $x \in S$.
 
* Consider the sets $S' = S \backslash \{x\}$, where $x$ is some element of $S$. We see that $|S'| = k$
        
* 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.
        
* 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.
        
* 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.
        
* Therefore: $\forall n \in \mathbb{N} : |S| = n \implies |\mathcal{P}(S)| = 2^n$
    
 A: 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.
A: I'll try to answer the question in a general manner, proceeding from the induction hypothesis.
Since $S'=S \backslash \{x\}$, then
\begin{equation}
S = S'\cup \{x\}
\quad .
\end{equation}
Recalling that
\begin{equation}
|S|=k+1
\quad ,
\end{equation}
it implies that
\begin{equation}
|S|=|S'\cup \{x\}|=|S'|+|\{x\}|=k+1
\end{equation}
since $S'$ and $\{x\}$ are pairwise disjoint, i.e., $S'\cap \{x\} = \varnothing$.
Then we can rewrite the power set of $S$ by
\begin{equation}
\mathcal{P}(S) = \mathcal{P}(S'\cup \{x\}) = \mathcal{P}(S') \cup \mathcal{P}(\{x\})\cup \mathcal{X}
\end{equation}
such  that
\begin{equation}
\mathcal{X} = \{A\in \mathcal{P}(S)|\exists B\in\mathcal{P}(S')[(A=B\cup\varnothing) \vee (A=B\cup\{x\})]\}
\quad .
\end{equation}
The set $\mathcal{X}$ is a set whose each element is an element of the power set of $S'$ with either the element of $\varnothing$ or $x$ adjoined (i.e., each element of all elements of $\mathcal{P}(\{x\})$ adjoin to each element of $\mathcal{P}(S')$).
Since the subformula $A=B\cup \varnothing$ in the set builder notation becomes $A=B$, it implies that a half of the elements of $\mathcal{X}$ is contained within $\mathcal{P}(S')$.
If we define
\begin{equation}
\mathcal{X}':=\{A\in \mathcal{P}(S)|\exists B\in\mathcal{P}(S')[A=B\cup\{x\}]\} =
\mathcal{X}\backslash\mathcal{P}(S')
\quad ,
\end{equation}
then we obtain
\begin{equation}
\mathcal{P}(S') \cup \mathcal{P}(\{x\})\cup \mathcal{X} = \mathcal{P}(S') \cup \mathcal{P}(\{x\})\cup \mathcal{X}'
\end{equation}
and hence
\begin{equation}
\mathcal{P}(S)=\mathcal{P}(S') \cup \mathcal{P}(\{x\})\cup \mathcal{X}'
\quad .
\end{equation}
Note that $\varnothing\notin\mathcal{X}'$, i.e., $\{\varnothing\}\cap\mathcal{X}'=\varnothing$, or $\{\varnothing\}\nsubseteq\mathcal{X}'$.
And also, the intersection between $\mathcal{P}(S')$ and $\mathcal{P}(\{x\})$ is nonempty, in fact the result is $\{\varnothing\}$, that is,
\begin{equation}
\mathcal{P}(S') \cap \mathcal{P}(\{x\})=\{\varnothing\}
\quad .
\end{equation}
On the other hand,
\begin{equation}
\mathcal{P}(\{x\})\cap\mathcal{X}'=\{x\}
\quad .
\end{equation}
Then we have
\begin{equation}
\mathcal{P}(\{x\})=\{\varnothing,\{x\}\}\subset\mathcal{P}(S')\cup\mathcal{X}'
\quad .
\end{equation}
Hence we obtain
\begin{equation}
\mathcal{P}(S)=
\mathcal{P}(S') \cup \mathcal{P}(\{x\})\cup \mathcal{X}'=
\mathcal{P}(S')\cup\mathcal{X}'
\quad .
\end{equation}
Since the definition of $\mathcal{X}'$ implies
\begin{equation}
\mathcal{P}(S')\cap\mathcal{X}'=\varnothing
\quad ,
\end{equation}
which means that $\mathcal{P}(S')$ and $\mathcal{X}'$ are pairwise disjoint, we have
\begin{equation}
\left|\mathcal{P}(S)\right|=\left|\mathcal{P}(S')\right|+\left|\mathcal{X}'\right|
\quad .
\end{equation}
Note that all the elements of $\mathcal{X}'$ are as many as all the elements of $\mathcal{P}(S')$, since each element of $\mathcal{X}'$ is actually each element of $\mathcal{P}(S')$ with $x$ adjoined.
\begin{equation}
\left|\mathcal{P}(S')\right| = \left|\mathcal{X}'\right|
\end{equation}
And by the induction hypothesis,
\begin{equation}
\left|\mathcal{P}(S')\right| = 2^k
\quad .
\end{equation}
Hence
\begin{equation}
\left|\mathcal{P}(S)\right|=
\left|\mathcal{P}(S')\right|+\left|\mathcal{X}'\right| =
2^k+2^k = 2\cdot 2^k =2^{k+1}
\end{equation}
completes the proof by mathematical induction.
Therefore
\begin{equation}
\forall n\in\mathbb{N}\left(|S|=n \implies |\mathcal{P}(S)=2^n\right)
\quad . \quad \Box
\end{equation}
