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

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 ofC \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.