1.2: Sets and set operations - Math 124 Course Notes

Sets¶

We can also form sets of non-numerical objects, such as

B=\{\text{red},\text{green},\text{blue}\}.

Here, we’ve seen a set of numbers and another set of colors; in this course, we may work with sets of numbers, points, vectors, and matrices.

In the definition of a set above, we said a set must be “well-defined” and contain “distinct” objects. What do these terms mean?

By well-defined, it means that there should be a clear way to check whether any object is in the set. If an object $x$ belongs to a set $S$ , we write $x\in S$ . If it does not, we write $x\notin S$ . For instance, $\text{blue} \in B$ and $\text{maize} \not \in B$ .
By distinct, we mean that sets do not contain duplicates. $\{2, 2, 4, 6, 6\}$ is not a valid set. They also do not keep track of order:

\{2,4,6\}=\{6,4,2\}.

Set-builder notation¶

Defining a set by listing every one of its elements called enumerative notation. Sometimes, we use ellipses (...) as a shortcut to writing out many elements, but it is only good practice to do this when it is clear what replaces the .... For example,

\{2, 4, 6, 8, ..., 20\}

is clearly the set containing all multiples of 2, starting with 2 and ending with 20. This is still considered enumerative notation. $\{2, 3, 5, ..., 10\}$ is more ambiguous. Try your best to avoid writing ambiguous statements – math is meant to be precise!

Often, enumerative notation is impractical, especially for sets with infinitely many elements. Set-builder notation describes a set by stating a rule that all of its elements follow. Recall, we earlier defined the set $A = \{2, 4, 6, 8\}$ . Now consider the set

C=\{6,12,18,24\}.

The elements of $C$ are just the elements of $A$ , each multiplied by 3. Using set-builder notation,

C=\{3x:x\in A\}.

The expression to the left of the colon describes what goes into the set; the condition to the right describes which values are allowed. (If you’re familiar with programming in Python – which you’re not expected to be! – this resembles the syntax for list comprehension. Don’t worry if this doesn’t mean anything to you.)

The general pattern for set-builder notation is

\{\text{what goes in the set}:\text{condition}\}.

Here are several other examples.

Using the same example set $C$ from above,
$\{x: x \in C, x > 10\}$
is the set of elements of $C$ that are greater than 10. This is the new set $\{12, 18, 24\}$ . The comma ( $,$ ) after the colon in the notation means “and”.
The set $\{10, 20, 30, ..., 100\}$ can be expressed in set-builder notation as
$\{10x: x \in \mathbb{Z}, 1 \leq x \leq 10 \}.$
$\mathbb{Z}$ is the set of all integers; we will discuss the set of integers (and other number sets) more in Chapter 1.3.
The set
$\{x: x \in \mathbb{Z}, x \geq 0\}$
is the set of all non-negative integers.
The set
$\{(x, y): x^2 + y^2 = 16, x \in \mathbb{R}, y \in \mathbb{R} \}$
is the set of all points on the circle with radius 4 centered at $(0, 0)$ . $\mathbb{R}$ refers to the set of real numbers, which again will be discussed in Chapter 1.3. For now, think of the real numbers as the set of all numbers that exist on a number line.

You’ll notice that in many of these examples, the item before the colon $:$ was simply $x$ , and following the colon were multiple conditions on $x$ , one of which was the set we were selecting elements from to create our new set (e.g. $C$ , $\mathbb{Z}$ , or $\mathbb{R}$ ). There is a shorter notation that is often used for sets like these. Here are a few examples.

Long-form	Shortform
$\{x: x \in C, x > 10\}$	$\{ x \in C : x > 10 \}$
$\{x: x \in \mathbb{Z}, x \geq 0\}$	$\{x \in \mathbb{Z}: x \geq 0\}$
$\{(x, y): x^2 + y^2 = 16, x \in \mathbb{R}, y \in \mathbb{R}\}$	$\{ (x, y) \in \mathbb{R}^2 : x^2 + y^2 = 16 \}$

In the final example, $\mathbb{R}^2$ is the set of all points in two-dimensional space.

The shortform notation is very common. To summarize, the two key forms you may see are:

$\{f(x): \text{conditions on } x \}$ (this is the first form we introduced above).
$\{x \in \mathbb{S}: \text{conditions on } x\}$ .

Activity 1

Write the set $\{k \in \mathbb{Z}: |k + 1| < 5\}$ using enumerative notation.
Write the set $\{2, 5, 10, 17, 26, 37, ...\}$ using set-builder notation. Try doing so in at least two different ways, each using a different formula before the $:$ .

Solutions

The set $\{k \in \mathbb{Z}: |k + 1| < 5\}$ in enumerative notation is
$\{-5, -4, -3, ..., 3\}.$
One way to write the set $\{2, 5, 10, 17, 26, 37, ...\}$ in set-builder notation is
$\{ x^2 + 1: x \in \mathbb{Z}, x \geq 1 \}.$
This is not the only way to write it! Another form is
$\{ (x-1)^2 + 1 : x \in \mathbb{Z}, x \geq 2 \},$
and yet another is
$\{ (x+1)^2 + 1: x \in \mathbb{Z}, x \geq 0 \}.$
All are equally good.

Subsets¶

For example, if $A=\{1,5,7,9,12\}$ and $B=\{7,12\}$ , then $B\subseteq A$ . On the other hand, $\{5,6\}\nsubseteq A$ because $6\notin A$ .

Two sets are equal precisely when they contain the same elements, or equivalently, they are both subsets of each other!

Every set is a subset of itself.
The empty set, $\emptyset$ , is the set with no elements in it. It is a subset of every set.

Activity 2

Recall, $\mathbb{Z}$ is the set of all integers, e.g. $\{..., -3, -2, -1, 0, 1, 2, 3. ...\}$ .

Let $A = \{x \in \mathbb{Z} : x > 2\}$ and $B = \{x \in \mathbb{Z}: x > 6\}$ . Is $A \subseteq B$ ? Is $B \subseteq A$ ? Both? Neither?
Let $C = \{x \in \mathbb{R} : x^2 > 4\}$ and $D = \{x \in \mathbb{R} : x > 2\}$ . Explain why it is not true that $C \subseteq D$ by finding one element in $C$ that is not in $D$ .

Solution

If $A = \{x \in \mathbb{Z} : x > 2\}$ and $B = \{x \in \mathbb{Z}: x > 6\}$ , then in enumerative notation,
$A = \{3, 4, 5, 6, 7, 8, 9, 10, ...\}, \quad B = \{7, 8, 9, 10, ...\}.$
Every element in $B$ is also in $A$ , so $B \subseteq A$ . The opposite is not true; $3 \in A$ but $3 \not \in B$ , so $A$ is not a subset of $B$ .
If $C = \{x \in \mathbb{R} : x^2 > 4\}$ and $D = \{x \in \mathbb{R} : x > 2\}$ , then $C$ includes all real numbers whose square is greater than 4, which also includes lots of negative numbers, like -3. But, -3 is not in $D$ , since $D$ only includes real numbers greater than 2, so $C$ cannot be a subset of $D$ .

Union and intersection¶

For example, if

A=\{1,5,7\}, \qquad B=\{2,3,7,8\},

then

A\cup B=\{1,2,3,5,7,8\}, \qquad A\cap B=\{7\}.

Two sets are disjoint if $A\cap B=\emptyset$ .

For any set $A$ ,

A\cup A=A, \qquad A\cup\emptyset=A, \qquad A\cap A=A, \qquad A\cap\emptyset=\emptyset.

To give you a sense of how this relates to the ideas in Chapter 1.1, soon we’ll describe lines and planes as sets of points. The intersection of two lines, then, can be viewed as the intersection of two sets!

Cardinality¶

Repetition does not affect cardinality, because sets do not store duplicates!

|\{1,1,2,2,2,12,-3,-3,9\}|=5.

For now, we’ll only consider the cardinality of finite sets. Sets with infinitely many elements, like the set of integers $\mathbb{Z}$ , do have some well-defined notion of cardinality, but we will save that discussion for a future theoretical mathematics or computer science course.

The principle of inclusion-exclusion¶

Given that we just discussed the union and intersection of two sets, a natural question is how $|A \cup B|$ and $|A \cap B|$ relate to $|A|$ and $|B|$ .

As a thought experiment, suppose $A$ and $B$ are two non-empty sets, and you are given that $|A \cup B| = |A| + |B|$ . What does this tell you about $A$ and $B$ ? (Pause and think for a moment before scrolling further.)

If $|A \cup B| = |A| + |B|$ , it means that there are no overlapping elements between $A$ and $B$ ! If there were overlapping elements, they each would have been counted for twice: once in $|A|$ and once in $|B|$ . But, since sets do not have duplicates, this would have overcounted those overlapping elements in $|A \cup B|$ . Thus, if $|A \cup B| = |A| + |B|$ , $A$ and $B$ are disjoint.

In the general case, when $A$ and $B$ are not necessarily disjoint, the principle of inclusion-exclusion tells us how to find $|A \cup B|$ , the number of elements in the union of $A$ and $B$ :

|A\cup B|=|A|+|B|-|A\cap B|.

Animated illustration of inclusion-exclusion for two sets.

Returning to our earlier example, if $A=\{1,5,7\}$ and $B=\{2,3,7,8\}$ , then

|A\cup B|=3+4-1=6.

This formula is more useful in cases where the sets are much larger and we can’t eyeball their intersections and unions.

How does this extend to three sets?

Animated illustration of inclusion-exclusion for three sets.

Like before, we subtract all pairwise overlaps, but then elements in all three sets have been removed too many times, so we add the triple overlap back once.

\begin{aligned} |A\cup B\cup C| ={}&|A|+|B|+|C|\\ &-|A\cap B|-|A\cap C|-|B\cap C|\\ &+|A\cap B\cap C|. \end{aligned}

Activity 3

Let $A=\{\text{dog}, \text{cat}, \text{hamster}, \text{zebra}\}$ and $B = \{\text{zebra}, \text{dolphin}, \text{rhino}, \text{dog}, \text{python}\}$ . Find $A \cup B$ , $A \cap B$ , and verify that the inclusion-exclusion formula holds.
Suppose $M$ is the set of 50 students in Math 124 this semester and $C$ is the set of 500 students in CHEM 210 this semester. If 45 students are in both classes, how many students are in at least one of the two classes? Express this quantity using the notation introduced in this section.

Solution

If $A=\{\text{dog}, \text{cat}, \text{hamster}, \text{zebra}\}$ and $B = \{\text{zebra}, \text{dolphin}, \text{rhino}, \text{dog}, \text{python}\}$ , then

$A \cup B = \{ \text{dog}, \text{cat}, \text{hamster}, \text{zebra}, \text{dolphin}, \text{rhino}, \text{python} \}$ , and $|A \cup B| = 7$ .
$A \cap B = \{ \text{dog}, \text{zebra} \}$ , and $|A \cap B| = 2$ .
$|A| = 4$ and $|B| = 5$ , and indeed,

\underbrace{7}_{|A \cup B|} = \underbrace{4}_{|A|} + \underbrace{5}_{|B|} - \underbrace{2}_{|A \cap B|}.

We’re given that $|M| = 50$ , $|C| = 500$ , and $|M \cap C| = 45$ . This means that
$|M \cup C| = |M| + |C| - |M \cap C| = 50 + 500 - 45 = 505$
students are in at least one of the two classes.