We want to develop a formula for the number of distinct subsets of a given set. We begin by considering a few examples to help us develop a pattern.
Example9.35.All subsets and the number of subsets.
We list all distinct subsets of certain sets and count these subsets to find the number of distinct subsets.
The only subset of \(\emptyset\) is \(\emptyset\text{.}\) Thus \(\emptyset\) has one subset.
The subsets of \(\{1\}\) are \(\emptyset\) and \(\{1\}\text{.}\) Thus \(\{1\}\) has two distinct subsets.
The subsets of \(\{1,2\}\) are \(\emptyset\text{,}\)\(\{1\}\text{,}\)\(\{2\}\text{,}\) and \(\{1,2\}\text{.}\) Thus \(\{1,2\}\) has four distinct subsets.
The subsets of \(\{1,2,3\}\) are \(\emptyset\text{,}\)\(\{1\}\text{,}\)\(\{2\}\text{,}\)\(\{3\}\text{,}\)\(\{1,2\}\text{,}\)\(\{1,3\}\text{,}\)\(\{2,3\}\text{,}\) and \(\{1,2,3\}\text{.}\) Thus \(\{1,2,3\}\) has eight distinct subsets.
In the video in Figure 9.36 we continue our investigation and present a formula for the number of subsets of a finite set. We give a detailed proof of the theorem below.
Figure9.36.Number of Subsets by Matt Farmer and Stephen Steward
In order to develop the desired formula for the number of distinct subsets of a given set, let us systematically consider how we can build up the lists of subsets for the sets in Example 9.35.
The set with no elements:.
We have already seen that \(\emptyset\) has the single subset \(\emptyset\text{.}\)
Sets with one element:.
If we put in one element, say \(a_1\text{,}\) to our set and consider the new set \(\{a_1\}\text{,}\) we still have the subset \(\emptyset\) from the previous set. However, we also have a new subset — the subset we get by including in that new element \(a_1\) to the existing subset. The new subset is \(\{a_1\}\text{,}\) giving us the two distinct subsets \(\emptyset\) and \(\{a_1\}\text{.}\)
Sets with two elements:.
Now, we do the same for a set with two elements. We consider the new set \(\{a_1,a_2\}\text{.}\) Just as the set \(\{a_1\}\) the set \(\{a_1,a_2\}\) has the subsets \(\emptyset\) and \(\{a_1\}\text{.}\) However, we also have two new subsets, namely the subsets we get by putting the new element \(a_2\) into the existing two subsets. The new subsets are \(\{a_2\}\) and \(\{a_1,a_2\}\text{,}\) giving us the four distinct subsets \(\emptyset\text{,}\)\(\{a_1\}\text{,}\)\(\{a_2\}\text{,}\) and \(\{a_1,a_2\}\text{.}\)
Sets with three elements:.
For clarity, we will do this one more time. If we put in the element \(a_3\) and consider the new set \(\{a_1,a_2,a_3\}\text{,}\) we still have the four subsets \(\emptyset\text{,}\)\(\{a_1\}\text{,}\)\(\{a_2\}\text{,}\) and \(\{a_1,a_2\}\) from the previous set. However, we also have four new subsets — the subsets we get by putting the new element \(a_3\) into the existing four subsets. The new subsets are \(\{a_3\}\text{,}\)\(\{a_1,a_3\}\text{,}\)\(\{a_2,a_3\}\text{,}\) and \(\{a_1,a_2,a_3\}\text{,}\) giving us the eight distinct subsets
\(\emptyset\text{,}\)\(\{a_1\}\text{,}\)\(\{a_2\}\text{,}\)\(\{a_1,a_2\}\text{,}\)\(\{a_3\}\text{,}\)\(\{a_1,a_3\}\text{,}\)\(\{a_2,a_3\}\) and \(\{a_1,a_2,a_3\}\)
Notice that each time we put in an extra element, we double the number of distinct subsets. We now show that this observation is true independent of the number of elements in the set without the extra element. We start with a set with \(n\) elements (for some \(n\in\N\)) and show that a set with \(n+1\) elements has twice as many distinct subsets.
Sets with \(n\) elements:.
Let \(A\) be a set that contains the \(n\) distinct elements \(a_1,a_2,a_3,\dots,a_n\text{,}\) that is, \(A=\{a_1,a_2,a_3,\dots,a_n\}\text{.}\) Assume we know that \(A\) has the \(m\) subsets \(S_1,\dots,S_m\text{.}\) Let \(a_{n+1}\) be an object not contained in \(A\text{.}\) From the list \(S_1,\dots,S_m\) of subsets of \(A\text{,}\) we construct all subsets of the set \(\{a_1,\dots,a_n,a_{n+1}\}\text{.}\) The subsets of \(\{a_1,\dots,a_{n+1}\}\) that do not contain \(a_{n+1}\) are \(S_1,\dots,S_m\text{.}\) So it remains to consider all subsets of \(\{a_1,\dots,a_n,a_{n+1}\}\) that contain \(a_{n+1}\text{.}\) Let \(T_1,\dots,T_m\) be the sets obtained by including the element \(a_{n+1}\) to \(S_1,\dots,S_m\text{,}\) respectively. Now, the \(2\cdot m\) sets \(S_1,\dots,S_m, T_1,\dots,T_m\) are all subsets of \(A\text{.}\)
With each additional element the number of subsets doubles, this observation yields the answer to the Checkpoint 9.37.
Checkpoint9.37.Number of subsets of a set with one more element.
Let \(A=\lbrace a_1, a_2, a_3, \dots, a_n\rbrace\text{.}\)
Let \(N\) be the number of distinct subsets of \(A\text{.}\)
Let \(b\) be an element not contained in \(A\text{.}\)
Let \(B=\lbrace a_1, a_2, a_3, \dots, a_n,b\rbrace\text{,}\) that is, \(B\) contains all elements of \(A\) and the additional element \(b\text{.}\)
What is the number of distinct subsets of \(B\) ?
\(\displaystyle N^2\)
\(\displaystyle N+2\)
\(\displaystyle N-2\)
\(\displaystyle N/2\)
\(\displaystyle N-1\)
\(\displaystyle 2\cdot N\)
\(\displaystyle N\)
\(\displaystyle N+1\)
Since the empty set has one subset and each additional element doubles the number of subsets, a set with \(n\) elements has
\begin{equation*}
1 \cdot\underbrace{2\cdot 2\cdot \ldots \cdot2}_{n\text{ copies of }2}=2^n
\end{equation*}
distinct subsets. We have proven the following result.
Theorem9.38.
The number of distinct subsets of a set \(A\) is \(2^{\nr{A}}\text{.}\)
This formula makes it easy for us to determine the number of subsets.
Problem9.39.The number of subsets of \(\Z_{11}^\otimes\).
Find the number of distinct subsets of \(\Z_{11}^\otimes\text{.}\)
Solution.
We have \(\Z_{11}^\otimes=\{1,2,3,\dots,10\}\text{.}\) So \(\nr{\Z_{11}^\otimes}=10\text{.}\) By the formula in Theorem 9.38 the number of distinct subsets of \(\Z_{11}^\otimes\) is
Thus the number of distinct subsets of \({9,10,11,...,17 }\) is:
The formulas for the number of distinct subsets also have more practical applications.
Problem9.41.Number of choices of pizza.
Mario’s Pizza offers the following toppings: onions, mushrooms, peppers, olives, and spinach. How many different types of pizza can be ordered using these toppings?
Solution.
Let \(T=\{\text{ onions }, \text{ mushrooms }, \text{ peppers }, \text{ olives }, \text{ spinach } \}\) be the set of toppings. Each pizza would be made using a subset of these toppings, so the number of different types of pizza that can be ordered would correspond to the number of distinct subsets of the set \(T\) of toppings. We have \(\nr{T}=5\text{.}\) So \(T\) has \(2^{\nr{T}}=2^5=32\) subsets. Thus 32 different pizzas can be ordered using these toppings.
Problem9.42.Number of choices of car options.
A person can order a new car with some, all, or none of the following options: air conditioning, power windows, satellite radio, leather interior, Bluetooth connectivity, and sun roof. How many different variations of the set of options are possible?
Solution.
Let \(O\) be the set of options. Since \(\#O=6\text{,}\) there are \(2^6=64\) distinct subsets of \(O\text{.}\) So, \(64\) different variations of the set of options are possible.
The Friendly Bike Store offers the options kickstand, fenders, bottle holder, hub dynamo, reflectors, hydraulic breaks, rack (back), and bell on its bikes.
Customers can choose between different combinations of options.
