Proving that all sets of size n have $2^n$ subsets I've tried to construct a proof for this using recursion. My knowledge of recursion and set theory in general is quite limited so I'd appreciate some feedback!
The claim in symbolic logic: $\forall n \in \mathbb N, \exists u \in U, S(u) \wedge |u| = n \Rightarrow \mathcal |P(u)| = 2^n$ where:
$U:$ the set of everything
$S(x):$ x is a set
Initial Value
Assume $n = 0$
Then $\exists u \in U, |u| = 0$
Then $ u = \varnothing $
Then $ |\mathcal P(u)| = | \{ \varnothing \} | = 1 = 2^0 $
Prove: $\forall n \in \mathbb N, \exists u, x \in U, [S(u) \wedge (x \notin u) \wedge (|u| = n) \wedge \mathcal |P(u)| = 2^n] \Rightarrow  [(|u \cup \{x\}| = n + 1) \wedge (|\mathcal P(u \cup \{x\})| = 2^{n + 1})]$ 
Assume $|u| = n$
Then $ |\mathcal P(u)| = 2^n$
Then $ |u \cup \{x\} | = n + 1$ because  $ |\{x\}| = 1$
Then $ \mathcal |P(u \cup \{x\})| = |\mathcal P(u)| * |\mathcal P(\{x\})| = 2^n * 2 = 2^{n+1} $
Is this convincing enough or do I need to add more? 
EDIT: Fixed notation
 A: Let $h_n$ be an $n$-bit string. i.e. A string consisting of 0's and 1's. Now let $S$ be your ground set with $n$ elements and $H \subseteq S$. If you label the elements of $S$ from 1 to $n$, given a fixed $H$, you can construct an $n$-bit string, say $h_n$ as follows, if $H$ has the 1st element, it has 1 in the first position and 0 otherwise. If $H$ has the second element, it has 1 in the 2nd position and 0 otherwise and so on...
For example if $S$ = {1,2,3,4,5,6} and $H$ = {2,4,6}, then $h_n$ is '010101'.
It is clear that given any subset, you can construct such an $n$-bit string. Conversely, given an $n$-bit string, you can construct a corresponding subset. In other words, there is a bijection from the set of $n$-bit strings to the set of all subsets of $S$. So the number of subsets of $S$ is equal to the number of $n$-bit strings which is $2^n$. 
Alternate proof by induction:
Let the statement hold for all $n$ element sets. i.e. if $\vert S \vert = n$ then $S$ has $2^n$ subsets. Now suppose you add one more element $x_{n+1}$ to $S$ and call that set $S'$. Then all the subsets of $S'$ will be subsets of $S$ either with or without the new element $x_{n+1}$. In other words, for every $H \subseteq S$, there will be two subsets $H'$ and $H''$ of $S'$ given by $H' = H$ and $H'' = H \cup \{x_{n+1}\}$. So if $S$ has $2^n$ subsets, $S'$ will have $2 \times 2^n = 2^{n+1}$ subsets. 
A: Recursion isn't neded here. If we have set of size $n$, then we can makes subsets of size $0,1,2,3...n$. Because the order of the elements in the set isn't important the number of ways we can choose subsets with size 0 is $\binom{n}{0}$. There are $\binom{n}{1}$ combinations for choosing subsets of size 1.
So the total number of subsets will be:
$$\sum_{k=0}^n \binom{n}{k} = 2^n$$
If you want a proof for this expression, here's one. Not that the sum is actually representing the sum of the numbers in $n^{th}$ row of the Pascal's triangle, where firs row is counted as 0. We know how to generate this triangle and we know that every number of the $n^{th}$ row is calculated twice in the sum of the next row. So the ratio between neighbour rows is $2$. This lead to geometric progresion: $ar^{n-1}$. We know that $a=1$ and $r=2$ so if we let our first row to be denoted as $n=0$, then the formula gets its final look:
$$\sum_{k=0}^n \binom{n}{k} = 2^n$$
A: First, do not use the concept of a "set of all sets."  Such a set cannot exist.  Please read this article for more info.
Second, start by letting $u_0 = \varnothing$ and $u_{i+1}=u_i \cup \{u_i\}$.  Specifically, note that this means that $u_2=\{\varnothing,\{\varnothing\}\}$.  Then you have guaranteed unique elements in $u_i$ for all $i$, and you can build an induction on it.  The powerset of $u_i$ and $u_{i+1}$ will be very easy to build and confirm as having $2^i$ and $2^{i+1}$ elements (respectively).
Finally, I believe that $|\mathcal P(u \cup \{x\})| = |\mathcal P(u)| * |\mathcal P(\{x\})|$ would need to be proven separately.
A: You can represent each subset of a set with $n$ elements by a sequence of $a_1...a_n$ where $a_i$ is either $0$ or $1$. $a_i=0$ means that the $i$th element of the set is not present in the subset. Now the number of all such sequences is $2\times 2\times ...\times 2=2^n$.
A: you have proved it for sets of size 0
now you have to prove:
if a set of  size n has $ 2^n $ different subsets
then a set of size n+1 has $ 2^{n+1} $ different subsets
and then you can use induction 
