# Prove that cardinality of power set of X is equal to $2^n$, $\left | \mathcal{P}(X) \right | = 2^n$, using the principle of mathematical induction

I have this,

Having a set $X$ with $n$ objects. The power set of $X$ has $2^n$ elements, i.e. the number of subsets of $X$ is $2^n$.

We can consider the following statement:
$$P(n) : \left | \mathcal{P}(X) \right | = 2^{n}$$

i) P(0) is true, in fact $\left | \mathcal{P}(X) \right | = 1$ i.e. it contains the empty set as unique element.

ii) Assuming true for $P(n-1)$, we have to prove for $n$. We can consider the set X with $n$ objects as the union of two sets : $Y = \left \{ a_1, a_2, \ldots, a_{n-1} \right \}$ and $\left \{ a_{n}\right \}$, hence,
$$X = \left \{ a_1, a_2, \ldots, a_{n-1} \right \} \cup \left \{ a_{n}\right \}$$

For inductive hypothesis the numbers of subsets of $Y$ is $2^{n-1}$, so it is true, but, I have problems in proving the truth for $2^n$.

Please, can you help me? Many thanks!

• You take all the old subsets and either add the new element or leave it out to form twice as many new subsets. Thus, since $|\mathcal P(Y)|=2^{n-1}$ this implies $|\mathcal P(Y\cup\{a_n\})|=2\cdot 2^{n-1}$. Done :o) – String Feb 19 '17 at 12:58
• To be more specific: Given $A\subseteq Y$ you can form two subsets, $A,A\cup\{a_n\}\subseteq Y\cup\{a_n\}$. – String Feb 19 '17 at 13:02

All the elements of $P(X)$ either contain $a_n$ or they do not.
1) There are $2^{n-1}$ elements of $P(X)$ that do not contain $a_n$ by the induction hypothesis.
2) Take any of the elements that do not contain $a_n$ and add $a_n$ to it. You get a new unique subset. There are $2^{n-1}$ elements that can be created this way, again by the induction hypothesis. These are all the elements of $P(X)$ that contain $a_n$.
In total there are thus $2^{n-1}+2^{n-1}=2^n$ elements in $P(X)$, which proves the statement.