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!
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.