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

Hint: We are going to solve this question by using mathematical induction for the given set $A$ to find how many power set in it. First, we have to know the definition of Power set is a set of all the subsets of the given set. In mathematics, the power set of any set $S$ is the set of all subsets of $S$, including the empty set and $S$ itself.

Complete step by step solution:
Initial case: For \[n = 0\]: First we are going to assume that the cardinality of the given set $A$ is 0.That is the set $A$ has no elements. Mathematically, we say this set as empty set. And it is denoted by \[\phi \].
So, we have \[\left| A \right| = 0 \Rightarrow A = \phi \].
We already know that the empty set has only one subset and it is itself.
Now we have that \[\left| {P\left( A \right)} \right| = 1\] . And we know that anything power 0 is 1. Therefore we can rewrite 1 as ${2^0}$. Here \[P(A)\] denotes the power set of \[A\] and \[\left| {P\left( A \right)} \right|\] denotes the cardinality of the power set.
Thus we have, \[\left| {P\left( A \right)} \right| = 1 = {2^0}\]
For \[n = 1\]: Now we assume that the set $A$ has only one element. So its power set has 2 elements.
That is, $A$ has subsets as empty set and the whole set $A$ itself.
Thus we have, \[\left| {P\left( A \right)} \right| = 2 = {2^1}\] (2 can be rewrite as\[{2^1}\])
For more clarification, we will see this with an example. Let us assume that $A = \left\{ {{a_1}} \right\}$
We already know that the power set of $A$ is the set of all subsets of $A$. Here $A$ has only one element ${a_1}$
So, Power set of $A$ contains 2 element that is two subsets. Those are ${a_1}$ and empty set \[\varphi \].
Therefore, we can clearly see that \[\left| {P\left( A \right)} \right| = 2 = {2^1}\].
For \[n = 2\]: Now we assume that the set $A$has only one element. So its power set has $3$ elements.
That is, $A$ has subsets as empty set, the whole set $A$ itself and combinations of double pair element sets.
Thus we have, \[\left| {P\left( A \right)} \right| = 3 = {2^3}\]
For more clarification, we will see this with an example.
Let us assume that for example,
If $A$ is the set $\{ x,y,z\} $, then the subsets of $A$ are:
$\{ \} $ (Also denoted the empty set or the null set)
$\{ x\} $
$\{ y\} $
$\{ z\} $
$\{ x,y\} $
$\{ x,z\} $
$\{ y,z\} $
$\{ x,y,z\} $
and hence the power set of $A$ is $\{ \{ \} ,{\text{ }}\{ x\}, {\text{ }}\{ y\}, {\text{ }}\{ z\}, {\text{ }}\{ x,y\}, {\text{ }}\{ x,z\}, {\text{ }}\{ y,z\}, {\text{ }}\{ x,y,z\} \}$.
Power set of $A$ contains $3$ element that is $8$ subsets. Those are $\{ x,y,z\} $ and empty set \[\phi \].
Therefore, we can clearly see that \[\left| {P\left( A \right)} \right| = 3 = {2^3}\].
Now we are going to assume that if the set $A$ contains n elements then its power set contains \[{2^n}\] elements.
Hence \[\left| {P\left( A \right)} \right| = {2^n}\] if \[A\] contains $n$elements.
Now we are going to check for $n + 1$elements. That is, if the set $A$ has $n + 1$ elements then its power set contains ${2^{n + 1}}$ elements. From this, we can conclude that if a non-empty set has n elements then its power set contains \[{2^n}\]elements by mathematical induction.
Let \[B\] be a set with \[\left( {n + 1} \right)\] elements, \[B = A \cup \left\{ a \right\}\]
\[B\]has two kinds of subsets. Those that include \['a'\] and those that do not include \['a'\]
The subsets that include\['a'\]are nothing but exactly the subsets of \[A\] and there are \[{2^n}\]elements of them.
The subsets that do not include\['a'\] are of the form of\[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 ′a′ is an element.
Therefore, \[\left| {P\left( B \right)} \right| = {2^n} + {2^n} = 2({2^n}) = {2^{n + 1}}\]
We proved that if a set has \[n + 1\]elements then its power set contains \[{2^{n + 1}}\] elements.

Hence by mathematical induction, we can conclude that if a set contains \[n\] elements then its power set contains \[{2^n}\] elements. Option ‘B’ is the correct answer.

Note:
Mathematical induction is a mathematical technique that is used to prove a formula or a statement is true for every natural number. This mathematical technique involves two steps.
Step 1: It proves that the given statement or formula is true for an initial value.
Step 2: It proves that if the given statement or formula is true for the ${n^{{\text{th}}}}$ iteration, then it is also true for ${(n + 1)^{{\text{th}}}}$ iteration.