Let X be a finite set. Show that P(X) has 2^|x| elements. Also, show that |2^x|=2^|x|.
{Hint: to give a rigorous proof, induct on the number of elements of X.}
A subset $\displaystyle A \subseteq X $ is determined by deciding whether each of the $\displaystyle n $ elements of $\displaystyle X $ is in the subset: there are two possibilities for each element $\displaystyle x $, namely $\displaystyle x \in A $ and $\displaystyle x \not \in A $. So the total number of possibilities for the subset $\displaystyle A $ is $\displaystyle 2 \times 2 \times \ldots \times 2 = 2^n $. So $\displaystyle |\mathcal{P}(X)| = 2^{|x|} $. Use this to be more rigorous.