Learning Objectives
The basics of subsets
- Number of distinct subsets
- The basics of proper subsets
- Number of distinct proper subsets
Subsets
Sometimes a collection might not contain all the elements of a set. For example, Chris owns three Madonna albums. While Chris’s collection is a set, we can also say it is a subset of the larger set of all Madonna albums.
Subsets of real numbers
The idea of subsets can also be applied to the sets of real numbers you studied previously. For example, the set of all whole numbers is a subset of the set of all integers. The set of integers in turn is contained within the set of rational numbers.
We say the integers are a subset of the rational numbers. You’ll see below in fact that the integers are a proper subset of the rational numbers.
Subset
A subset of a set A is another set that contains only elements from the set A, but may not contain all the elements of A.
If B is a subset of A, we write B ⊆ A
A proper subset is a subset that is not identical to the original set—it contains fewer elements.
If B is a proper subset of A, we write B ⊂ A
Note: a subset contains more elements than a proper subset. Therefore, thinking of the line underneath as an equivalence symbol can be helpful.
Example
Consider these three sets:
A = the set of all even numbers
B = {2, 4, 6}
C = {2, 3, 4, 6}
Here B ⊂ A since every element of B is also an even number, so is an element of A.
More formally, we could say B ⊂ A since if x ∈ B, then x ∈ A.
It is also true that B ⊂ C.
C is not a subset of A, since C contains an element, 3, that is not contained in A
Example
Suppose a set contains the plays “Much Ado About Nothing,” “MacBeth,” and “A Midsummer’s Night Dream.” What is a larger set this might be a subset of?
Try It
Consider the set [latex]A = \{1, 3, 5\} [/latex]. Which of the following sets is [latex]A [/latex] a subset of?
[latex]X = \{1, 3, 7, 5\} [/latex]
[latex]Y = \{1, 3 \} [/latex]
[latex]Z = \{1, m, n, 3, 5\}[/latex]
Exercises
Given the set: A = {a, b, c, d}. List all of the subsets of A
Listing the sets is fine if you have only a few elements. However, if we were to list all of the subsets of a set containing many elements, it would be quite tedious. Instead, in the next example we will consider each element of the set separately.
Example
In the previous example, there are four elements. For the first element, a, either it’s in the set or it’s not. Thus there are 2 choices for that first element. Similarly, there are two choices for b—either it’s in the set or it’s not. Using just those two elements, list all the possible subsets of the set {a,b}
Recall exponential notation
Now let’s include c, just for fun. List all the possible subsets of the new set {a,b,c}.
Again, either c is included or it isn’t, which gives us two choices. The outcomes are {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}. Note that there are [latex]2^{3}=8[/latex] subsets.
If you include four elements, there would be [latex]2^{4}=16[/latex] subsets. 15 of those subsets are proper, 1 subset, namely {a,b,c,d}, is not.
Number of Subsets
Number of Subsets
First, subsets are smaller collections of a sets’ elements.
For example, suppose set A = {red, yellow, blue}. To find all the subsets, just list all the possible combinations of elements:
1. { } (This is the empty set. The empty set is a subset of all sets.)
2. {red}
3. {yellow}
4. {blue}
5. {red, yellow}
6. {red, blue}
7. {yellow, blue}
8. {red, yellow, blue} (Yes, the set can be a subset of itself!)
Notice there were 8 possible combinations of elements, including the empty set. It turns out that all sets with 3 elements have 8 possible combinations of elements.
Here’s the pattern on how you figure out the number of distinct subsets that a set has:
A set with this many elements… | Has this many distinct subsets… |
1 | 2 (this is 21 ) |
2 | 4 (this is 22 or 2 x 2) |
3 | 8 (this is 23 or 2 x 2 x 2) |
4 | 16 (this is 24 or 2 x 2 x 2 x 2) |
n, where is any whole number | 2n (you can use the exponent key on your calculator to find 2n ) |
The number of distinct subsets of a finite set A is 2n .
Number of Distinct Proper Subsets
An important fact to remember about proper subsets is that every set is a subset of itself, HOWEVER, no set is a proper subset of itself.
Consider, again, the set A = {red, yellow, blue}. To find all the possible proper subsets, just list all the possible combinations of elements, but do NOT include the set itself:
1. { } (This is the empty set. The empty set is a subset of all sets.)
2. {red}
3. {yellow}
4. {blue}
5. {red, yellow}
6. {red, blue}
7. {yellow, blue}
Notice that {red, yellow, blue} is not listed in the proper subsets. So, to find the number of distinct proper subsets subtract 1 from the number of distinct subsets. So, the number of distinct proper subsets of a finite set A is 2n – 1.
Example
Suppose you went out for pizza. There were only four possible toppings: pepperoni, sausage, olives, and mushrooms. How many different variations of pizza are there?
YOU TRY
Suppose you went to an all-you-can-eat buffet with the following items: cashew chicken (CC), shrimp fried rice (SFR), sweet and sour pork (SSP), broccoli with garlic sauce (BGS), and egg rolls (ER).
a) Using the appropriate formula, show how you could calculate the number of variations on your plate without listing them out.
b) List the possible variations that you could put on your plate.
c) Would these variations be considered subsets or proper subsets, and why?
This is the end of the section. Close this tab and proceed to the corresponding assignment.