Question

If a non-empty set $A$ contains $n$ elements, then its power set contains how many elements?

• A. $n^2$
• B. $2^n$
• C. $2n$
• D. $n+1$

Answer 1

Answer: (B)

$2^n$

If a non-empty set $A$ contains $n$ elements, then its power set contains $2^n$ elements.
This can be proved using mathematical induction.
Base Case$:$ suppose $\left|A\right|=0⟹A=\varphi$. But, empty set is only subset of itself. So, $\left|P\left(A\right)\right|=1=2^0.$
Now, suppose $\left|A\right|=n$.
By induction hypothesis, we know that $\left|P\left(A\right)\right|=2^n⟶1$
Let $B$ be a set with $(n+1)$ elements, $B=A\cup \left\{a\right\}$
Now, there are $2$ kinds of subsets of $B:$ those that include ${}^{\prime }{a}^{\prime }$ and those that don't.
The first ones are exactly the subsets of $X$ which do not contain ${}^{\prime }{a}^{\prime }$ and there are $2^n$ of them.
The second one are of the form $C\cup \left\{a\right\},$ where $C\in P\left(A\right).$ since there are $2^n$ possible choices for $C,$ there must be exactly $2^n$ subsets of B of which ${}^{\prime }{a}^{\prime }$ is an element.
$\therefore \left|P\left(B\right)\right|=2^n+2^n=2^{n+1}.$
so, if set has $n$ elements, then power set has $2^n$ elements.
Hence proved.