maths.free › Set Theory & Logic › 1. Sets › Subsets

Subsets

Represent subsets and proper subsets symbolically.

Learning Objectives

After completing this section, you should be able to:

Represent subsets and proper subsets symbolically.
Compute the number of subsets of a set.
Apply concepts of subsets and equivalent sets to finite and infinite sets.

Exponential Notation

So far, we have figured out how many subsets exist in a finite set by listing them. Recall that in , when we listed all the subsets of the three-element set $L=\{newspaper, magazine, book\}$ we saw that there are eight subsets. In Your Turn 1.11, we discovered that there are four subsets of the two-element subset, $S=\{heads, tails\}$. A one-element set has two subsets, the empty set and itself. The only subset of the empty set is the empty set itself. But how can we easily figure out the number of subsets in a very large finite set? It turns out that the number of subsets can be found by raising 2 to the number of elements in the set, using exponential notation to represent repeated multiplication. For example, the number of subsets of the set $L=\{newspaper, magazine, book\}$ is equal to ${2}^{3}=2⋅2⋅2=8$. Exponential notation is used to represent repeated multiplication, ${b}^{n}=b⋅b⋅b⋅\ldots ⋅b$, where $b$ appears as a factor $n$ times.

Computing the Number of Subsets of a Set

Try it.

Find the number of subsets of each of the following sets.

The set of top five scorers of all time in the NBA: $S=\{LeBron James, Kareem Abdul-Jabbar, Karl Malone, Kobe Bryant, Michael Jordan\}\text{.}$
The set of the top four bestselling albums of all time: $A=\{Thriller, Hotel California, The Beatles White Album, Led Zepplin IV\}$.
$R=\{Snap, Crackle, Pop\}$.

Solution

$n(S)=5$. So, the total number of subsets of $S\ \text{is}\ {2}^{5}=2⋅2⋅2⋅2⋅2=32$.
$n(A)=4$. Therefore, the total number of subsets of $A\ \text{is}\ {2}^{4}=16$.
$n(R)=3$. So, the total number of subsets of $R\ \text{is}\ {2}^{3}=8$.

Equivalent Subsets

In the early 17th century, the famous astronomer Galileo Galilei found that the set of natural numbers and the subset of the natural numbers consisting of the set of square numbers, ${n}^{2}$, are equivalent. Upon making this discovery, he conjectured that the concepts of less than, greater than, and equal to did not apply to infinite sets.

Sequences and series are defined as infinite subsets of the set of natural numbers by forming a relationship between the sequence or series in terms of a natural number, $n$. For example, the set of even numbers can be defined using set builder notation as $\{a|a=2n\ \text{where}\ n\ \text{is a natural number}\}$. The formula in this case replaces every natural number with two times the number, resulting in the set of even numbers, $\{2,4,6,\ldots \}$. The set of even numbers is also equivalent to the set of natural numbers.

Subsets

Every member of a subset of a set is also a member of the set containing it. $A⊆B$
A proper subset of a set does not contain all the members of the set containing it. There is a least one member of set $B$ that is not a member of set $A$. $A⊂B$
The number subsets of a finite set $A$ with $n(A)$ members is equal to 2 raised to the $n(A)$ power.
The empty set is a subset of every set and must be included when listing all the subsets of a set.
Understand how to create and distinguish between equivalent subsets of finite and infinite sets that are not equal to the original set.

Formulas

The number of subsets of a finite set $A$ is equal to 2 raised to the power of $n(A)$, where $n(A)$ is the number of elements in set $A$: Number of Subsets of Set $A={2}^{n(A)}$.

Practice (7)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

Set $L$ is a set of reading materials available in a shop at the airport, $L=\{\text{newspaper, magazine, book}\}$. List all the subsets of set $L$.

Хариулт

Step 1: It is best to begin with the set itself, as every set is a subset of itself. In our example, the cardinality of set $L$ is $n(L)=3$. There is only one subset of set $L$ that has the same number of elements of set $L:\{\text{newspaper},\text{magazine},\text{book}\}$.
Step 2: Next, list all the proper subsets of the set containing $n(L)-1$ elements. In this case, $3-1=2$. There are three subsets that each contain two elements: $\{\text{newspaper},\text{magazine}\}$, $\{\text{newspaper},\text{book}\}$, and $\{\text{magazine},\text{book}\}$.
Step 3: Continue this process by listing all the proper subsets of the set containing $n(L)-2$ elements. In this case, $3-2=1$. There are three subsets that contain one element: $\{\text{newspaper}\}$, $\{\text{magazine}\}$, and $\{\text{book}\}$.
Step 4: Finally, list the subset containing 0 elements, or the empty set: $\{\ \}$.
Consider the set of common political parties in the United States, $P=\{Democratic, Green, Libertarian, Republican\}$. Determine if the following sets are proper subsets of $P$.
1. $M=\{Democratic, Republican\}$
2. $G=\{\text{Green}\}$
3. $V=\{Republican, Libertarian, Green, Democratic\}$
Хариулт
1. $M$ is a proper subset of $P$, written symbolically as $M⊂P$ because every member of $M$ is a member of set $P$, but $P$ also contains at least one element that is not in $M$.
2. $G$ is a single member proper subset of $P$, written symbolically as $G⊂P,$ because Green is a member of set $P$, but $P$ also contains other members (such as Democratic) that are not in $G$.
3. $V$ is subset of $P$ because every member of $V$ is also a member of $P$, but it is not a proper subset of $P$ because there are no members of $V$ that are not also in set $P$. We can represent the relationship symbolically as $V⊆P,$ or more precisely, set $V$ is equal to set $P$, $V=P.$
Consider the subsets of a standard deck of cards: $S=\{spades, hearts, diamonds, clubs\}$; $R=\{hearts, diamonds\}$; $B=\{spades, clubs\}$; and $C=\{\text{clubs}\}$.
Express the relationship between the following sets symbolically.
1. Set $S$ and set $B$.
2. Set $C$ and set $B$.
3. Set $R$ and $R$.
Хариулт
1. $B⊂S$. $B$ is a proper subset of set $S$.
2. $C⊂B$. $C$ is a proper subset of set $B$.
3. $R⊆R\ \text{or}\ R=R$. $R$ is subset of itself, but not a proper subset of itself because $R$ is equal to itself.
Find the number of subsets of each of the following sets.
1. The set of top five scorers of all time in the NBA: $S=\{LeBron James, Kareem Abdul-Jabbar, Karl Malone, Kobe Bryant, Michael Jordan\}\text{.}$
2. The set of the top four bestselling albums of all time: $A=\{Thriller, Hotel California, The Beatles White Album, Led Zepplin IV\}$.
3. $R=\{Snap, Crackle, Pop\}$.
Хариулт
1. $n(S)=5$. So, the total number of subsets of $S\ \text{is}\ {2}^{5}=2⋅2⋅2⋅2⋅2=32$.
2. $n(A)=4$. Therefore, the total number of subsets of $A\ \text{is}\ {2}^{4}=16$.
3. $n(R)=3$. So, the total number of subsets of $R\ \text{is}\ {2}^{3}=8$.
Using natural numbers, multiples of 3 are given by the sequence $\{3, 6, 9, \ldots \}$. Write this set using set builder notation by expressing each multiple of 3 using a formula in terms of a natural number, $n$.

Хариулт

$\{m|m=3n\ \text{where}\ n\ is a natural number\}$ or $\{m|m=3n\ \text{where}\ n\in N\}$. In this example, $m$ is a multiple of 3 and $n$ is a natural number. The symbol $\in$ is read as “is a member or element of.” Because there is a one-to-one correspondence between the set of multiples of 3 and the natural numbers, the set of multiples of 3 is an equivalent subset of the natural numbers.
A fast-food restaurant offers a deal where you can select two options from the following set of four menu items for $6: a chicken sandwich, a fish sandwich, a cheeseburger, or 10 chicken nuggets. Javier and his friend Michael are each purchasing lunch using this deal. Create two equivalent, but not equal, subsets that Javier and Michael could choose to have for lunch.

Хариулт

The possible two-element subsets are: {chicken sandwich, fish sandwich}, {chicken sandwich, cheeseburger}, {chicken sandwich, chicken nuggets}, {fish sandwich, cheeseburger}, {fish sandwich, chicken nuggets}, and {cheeseburger, chicken nuggets}. One possible solution is that Javier picked the set {chicken sandwich, chicken nuggets}, while Michael chose the {cheeseburger, chicken nuggets}. Because Javier and Michael both picked two items, but not exactly the same two items, these sets are equivalent, but not equal.
A high school volleyball team at a small school consists of the following players: {Angie, Brenda, Colleen, Estella, Maya, Maria, Penny, Shantelle}. Create two possible equivalent starting line-ups of six players that the coach could select for the next game.

Хариулт

There are actually 28 possible ways that the coach could choose his starting line-up. Two such equivalent subsets are {Angie, Brenda, Maya, Maria, Penny, Shantelle} and {Angie, Brenda, Colleen, Estella, Maria, Shantelle}. Each subset has six members, but they are not identical, so the two sets are equivalent but not equal.

Symbols used here

\neq

not equal
The two sides are different.

\infty

infinity
Not a number: "grows without bound" in limits and intervals.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

How to: Subsets

Represent subsets and proper subsets symbolically.
Compute the number of subsets of a set.
Apply concepts of subsets and equivalent sets to finite and infinite sets.
Set
Set
Set
The set of top five scorers of all time in the NBA:
The set of the top four bestselling albums of all time:

Questions people ask

Are some infinities bigger than others?

Yes. The integers and the rationals can be listed; the real numbers cannot (Cantor's diagonal argument), so there are strictly more reals than integers.

What is the difference between a relation and a function?

A relation pairs inputs with outputs freely; a function is a relation in which every input gets exactly one output.

Өөрийнхөөг турш

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

Бүх зүйл Set Theory & Logic

Sets and operations Relations, functions and equivalence Cardinality and infinity Logic and methods of proof