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!

  • $\begingroup$ 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) $\endgroup$ – String Feb 19 '17 at 12:58
  • $\begingroup$ To be more specific: Given $A\subseteq Y$ you can form two subsets, $A,A\cup\{a_n\}\subseteq Y\cup\{a_n\}$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.