1.2 Subsets

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

Recall that the expression [latex]a^{m}[/latex] states that some real number [latex]a[/latex] is to be used as a factor [latex]m[/latex] times.
Ex. [latex]2^{5} = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32[/latex]

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.

In general, if you have n elements in your set, then there are [latex]2^{n}[/latex] subsets and [latex]2^{n}−1[/latex] proper subsets.

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.