2.2 Algebra of Sets
Now that we understand the basic definitions involving sets, we examine set operations. These will allow us to create new sets from given sets.
Definition 2.4 Let \(A\) and \(B\) be sets. We define the union of \(A\) and \(B\), denoted \(A \cup B\), to be the set of elements that are either in \(A\) or \(B\), or possibly both. We define the intersection of \(A\) and \(B\), \(A \cap B\), to be the set of elements that are in both \(A\) and \(B\). We say that \(A\) and \(B\) are disjoint (or mutually exclusive) if \(A\cap B = \emptyset\).
Note that in the English language that the word ‘or’ is often understood in an exclusionary way. If someone asks if you would like red grapes or green grapes, there is an implication that you have to choose one or the other, but not both. In mathematics, the word ‘or’ is an inclusive word with the implication that you can be in both sets.
The shaded regions in Figure 2.4 illustrate each set relationship in terms of general sets \(A\) and \(B\). We can also write the union and intersection of sets in terms of set-builder notation: \[A\cup B = \{x \vert x\in A \mbox{ or } x\in B\} \quad \mbox{ and } \quad A\cap B =\{x\vert x\in A \mbox{ and } x\in B\}.\]
Figure 2.4: The union and intersection of two sets
Let’s look at a couple of examples to better understand these unions and intersections.
Example 2.4 Let \(A = \{a, b, c, d, e\}\) and \(B = \{ d, e, f, g\}\). Then \[A\cup B=\{a, b, c, d, e, f, g\} \]
Example 2.5 Let \(A=\{1,2,3,4,5,6,7,8,9\}\) and \(B=\{2,4,6,8\}\). Then \[A \cup B = A \quad \mbox{ and } \quad A\cap B = B.\]
Example 2.6 Let \(A=\{a,b,c\}\) and \(B=\{1,2,3\}\). Then \[A\cup B = \{a,b,c,1,2,3\} \quad \mbox{ and } \quad A\cap B =\emptyset.\]
Example 2.7 Let \(A = \{ x\in \mathbb{R} \: \vert \: x > 5\}\) and \(B=\{x \in \mathbb{R} \: \vert \: x < 8\}\), also denoted as \((5,\infty)\) and \((-\infty, 8)\), respectively. Then \(A\cup B\) would be all real numbers, since any real number is either less than 8 or greater than 5. And \(A\cap B\) would be the real numbers between 5 and 8. These can also be represented on number lines, where the shaded lines and filled dots are included in the set, with open dots and unshaded lines not being included in the set.
The following theorem identifies properties of the union as an operation on sets that follow from the definition.
Theorem 2.2 Let \(A\), \(B\), and \(C\) be sets. Then we have the following:
\(A\cup \emptyset = A\)
\(A \cup A = A\)
\(A \cup B = B \cup A\)
\(A \cup (B\cup C ) = (A\cup B) \cup C\)
\(A \subseteq A \cup B\)
If \(A \subseteq B\), then \(A\cup B=B\)
Proof. The first two statements follow directly from the definition of the union. The empty set has no elements, making its union with \(A\) equal to \(A\). Because \(A\) and \(A\) have the same elements, the union must also be \(A\).
The third statement suggests that the set operation “union” is commutative, in that the order of the operation does not matter. The proof follows from properties of symbolic logic in relation to the use of the “or” statement in the definition of the union.
The fourth statement in the theorem is used to expand the definition of union, which is only defined for a pair of sets, to more than two sets. A further consequence of statement four is that the method of pairing sets the under the operation of union is irrelevant. We show this by proving the two statements \(A \cup (B\cup C ) \subseteq (A\cup B) \cup C\) and \((A\cup B) \cup C \subseteq A \cup (B\cup C)\) (see Theorem 2.1). In order to show the first containment, we let \(x\in A \cup (B\cup C )\) be a generic element. Then by the definition of the union of sets, \(x\in A\) or \(x\in (B\cup C)\). We will then break this statement into two cases.
Case 1. If \(x\in A\), then by the definition of unions \(x\in (A \cup B)\). Then using the definitions of unions again, \(x \in ((A \cup B) \cup C)\).
Case 2. If \(x\in (B\cup C)\), then \(x\in B\) or \(x\in C\). If \(x\in B\), then \(x\in (A\cup B)\) and also \(x\in ((A\cup B) \cup C)\). If \(x\in C\), then \(x\in ((A\cup B) \cup C)\).
So in either case, \(x \in A \cup (B\cup C)\) implies that \(x\in (A\cup B) \cup C\). So \(A\cup (B\cup C) \subseteq (A\cup B)\cup C\). The proof of the reverse containment is nearly identical.
We leave the last two statements as exercises.
Similar to the union, the following theorem demonstrates how the intersection of sets works as an operation on sets. The proofs for each statement are similar to that of the unions so we will leave the proof of this theorem as an exercise.
Theorem 2.3 Let \(A\), \(B\), and \(C\) be sets. Then we have the following
\(A\cap \emptyset = \emptyset\)
\(A \cap A = A\)
\(A \cap B = B \cap A\)
\(A \cap (B\cap C ) = (A\cap B) \cap C\)
If \(A \subseteq B\), then \(A \cap B = A\)
Now that we know how unions and intersections behave by themselves, we examine how they interact with each other.
Theorem 2.4 Let \(A\), \(B\), and \(C\) be sets. Then \[ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \quad \mbox{ and } \quad A \cup (B \cap C) = (A \cup B) \cap (A \cup C).\]
These relationships are diagrammed in Figure 2.5.
Figure 2.5: Venn Diagrams for Set Distribuions
Proof. As each of these are proofs of equality of sets, we will need to complete the proofs showing that each set is contained in the other (see Theorem 2.1). We prove Part 1 and leave Part 2 as an exercise.
Let \(x\in A \cap (B \cup C)\). Then \(x\in A\) and \(x\in (B\cup C)\). This yields two cases: \(x\in A\) and \(x\in B\), or \(x\in A\) and \(x\in C\). This is equivalent to \(x \in (A\cap B) \cup (A\cap C)\). Thus \(A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)\).
If \(x\in (A \cap B) \cup (A \cap C)\), then we have to examine two cases: \(x\in (A\cap B)\) or \(x\in (A \cap C)\).
Case 1. If \(x\in (A\cap B)\), then \(x\in A\) and \(x\in B\). Since \(x\in B\), we know that \(x\in (B\cup C)\). Thus \(x\in A \cap (B\cup C)\).
Case 2. If \(x \in (A\cap C)\), then \(x\in A\) and \(x\in C\). Since \(x\in C\), we know that \(x \in (B\cup C)\). Thus \(x \in A \cap (B\cup C)\).
These results imply that \((A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)\). Thus, the Part 1 of the theorem is proven.
2.2.1 Set Complements
When working on a problem, we usually describe several sets, with an underlying assumption that the sets referenced contain elements from some common, larger set. We call a set that contains all of the elements considered for a particular situation a universal set.
Definition 2.5 For every set \(A\) that is a subset of the universal set \(U\), we define the complement of \(A\) to be the set of elements in the universal set that are not in \(A\), denoted \[A^c=\left\{ x\in U \middle \vert x \notin A\right\}.\]
Figure 2.6: Set Complement and Set Difference
For a given set \(A\) in universal set \(U\), the complement of a set identifies everything that is in the universal set except for things in set \(A\). This is often useful; however, there are times when it is important to consider the elements that are in one set, but not in another, without reference to the universal set.
Definition 2.6 Let \(A\) and \(B\) be sets. The complement of \(A\) with respect to \(B\), also called the set difference of \(B\) and \(A\), is defined as \[B\setminus A = B \cap A^c = \left\{x\in B \middle \vert x \notin A\right\}.\]
Note that this can be read of as “\(B\), not including \(A\)” or as “\(B\) minus \(A\).”
Let’s revisit our previous examples to understand this idea of a set difference.
Example 2.8 Let \(A = \{a, b, c, d, e\}\) and \(B = \{ d, e, f, g\}\). Then \[A\setminus B=\{a, b, c\} \quad \mbox{ and } \quad B\setminus A =\{ f, g\}.\]
Example 2.9 Let \(A=\{1,2,3,4,5,6,7,8,9\}\) and \(B=\{2,4,6,8\}\). Then \[A \setminus B = \{1,3,5,7,9\} \quad \mbox{ and } \quad B\setminus A = \emptyset.\]
Example 2.10 Let \(A=\{a,b,c\}\) and \(B=\{1,2,3\}\). Then \[A\setminus B = A \quad \mbox{ and } \quad B\setminus A =B.\]
2.2.2 De Morgan’s Laws
In the same year as the seminal work of Boole -Boole (1847) that started mathematics as a theoretical discipline, Augustus De Morgan published a foundational work in logic (De Morgan, 1847). In this book, De Morgan defines and describes symbolic mathematical logic. His work has become the foundation for our current mathematical system. One of the key components of this work examines the complements of intersections and unions (De Morgan, 1847, p. 69).
Theorem 2.5 If \(A\) and \(B\) are subsets of the same universal set, then \[ \left(A \cap B\right)^c = A^c \cup B^c \quad \mbox{and} \quad \left(A \cup B \right)^c = A^c \cap B^c.\]
Proof. Because we are proving that two sets are equal we need to prove that the sets are subsets of each other. Here we will prove that \(\left(A \cap B\right)^c = A^c \cup B^c\) and leave the other proof as an exercise.
(Proof that \(\left(A \cap B\right)^c \subseteq A^c \cup B^c\).):
Let \(x\in \left(A \cap B\right)^c\). So \(x\) is not in \(A\cap B\). \(x\) is not in both \(A\) and \(B\).
Case 1. If \(x\in A\), then \(x\notin B\). So \(x\in B^c\).
Case 2. If \(x\notin A\), then \(x\in A^c\).
So either way, \(x\) is in \(A^c\) or \(x\) is in \(B^c\) (\(x\in A^c \cup B^c\)). Therefore, \(\left(A \cap B\right)^c \subseteq A^c \cup B^c\).
(Proof that \(A^c \cup B^c \subseteq \left(A \cap B\right)^c\).):
Let \(x \in A^c \cup B^c\).
Case 1. \(x\in A^c\). Then \(x\notin A\). So \(x\notin A\cap B\). So \(x\in (A\cap B)^c\).
Case 2. \(x\in B^c\). Then \(x\notin B\). So \(x\notin A\cap B\). So \(x\in A\cap B)^c\).
Therefore, \(A^c \cup B^c \subseteq \left(A \cap B\right)^c\)
Therefore, \(\left(A \cap B\right)^c = A^c \cup B^c\).
It is also helpful to understand De Morgan’s laws by looking at the corresponding Venn diagrams, shown in Figure 2.7.
Figure 2.7: Venn diagrams for De Morgan’s laws for pairs of sets
2.2.3 Cartesian Products
The previous sections have considered set operations between two sets that exist in the same universal set. Sets can also be combined to create new sets that exist in a universal set that differs from those of the sets used to create it. The collection of set operations that do this allows us to use sets to create multidimensional systems such as ordered pairs.
Definition 2.7 The Cartesian Product of two non-empty sets \(A\) and \(B\) is the set \[A\times B = \left\{ (a,b) \middle \vert a \in A, b\in B\right\}\] of all ordered pairs of elements where the first coordinate in the pair comes from the set \(A\) and the second coordinate is an element of \(B\).
The Cartesian product, \(A\times B\), is often read as “\(A\) cross \(B\)”.
The most common Cartesian product in the secondary mathematics curriculum is real plane (often called the Cartesian plane or coordinate plane), \(\mathbb{R} \times \mathbb{R}\), which is often denoted by \[\mathbb{R}^2:= \left\{ (x,y) \vert x,y\in \mathbb{R} \right\}.\]
Note that the symbol \(:=\) is read as “defined to be equal to” and is a short hand for definitions in mathematics.
Related Content Standards
- (5.G.1) Use a pair of perpendicular number lines, called axes, to define a coordinate system, with the intersection of the lines (the origin) arranged to coincide with the \(0\) on each line and a given point in the plane located by using an ordered pair of numbers, called its coordinates. Understand that the first number indicates how far to travel from the origin in the direction of one axis, and the second number indicates how far to travel in the direction of the second axis, with the convention that the names of the two axes and the coordinates correspond (e.g., \(x\)-axis and \(x\)-coordinate, \(y\)-axis and \(y\)-coordinate).
The concept of the Cartesian product can be generalized to more than a pair of sets, for example \[\mathbb{R}^3:= \left\{ (x,y,z) \vert x,y,z\in \mathbb{R} \right\}\] is the three dimensional Cartesian space where each coordinate is a real number.
Theorem 2.6 It is sometimes helpful to summarize all of the properties of algebra on sets into a single location.
Let all sets referred to below be subsets of a universal set \(U\).
(Commutative Laws) For all sets \(A\) and \(B\), \[(a) \: A \cup B = B \cup A \quad \mbox{and} \quad (b) \: A \cap B = B \cap A\]
(Associative Laws) For all sets \(A\), \(B\), and \(C\), \[(a) \: (A\cup B)\cup C = A \cup (B \cup C) \quad \mbox{and} \quad (b) \: (A \cap B) \cap C = A \cap (B\cap C)\]
(Distributive Laws) For all sets \(A\), \(B\), and \(C\), \[(a) \: A \cup (B \cap C) = (A \cup B)\cap (A \cup C) \quad \mbox{and} \quad (b) \: A \cap (B \cup C) = (A \cap B)\cup (A \cap C)\]
(Identity Laws) For all sets \(A\), \[(a) \: A \cup \emptyset = A \quad \mbox{and} \quad (b) \: A \cap U = A\]
(Complement Laws) \[(a) \: A \cup A^c = U \quad \mbox{and} \quad (b) \: A \cap A^c = \emptyset\]
(Double Complement Law) For all sets \(A\), \[(A^c)^c =A\]
(Idempotent Laws) For all sets \(A\), \[(a) \: A\cup A=A \quad \mbox{and} \quad (b) \: A \cap A =A\]
(Universal Bound Laws) For all sets \(A\), \[(a) \: A \cup U = U\quad \mbox{and} \quad (b) \: A \cap \emptyset = \emptyset\]
(De Morgan’s Laws) For all sets \(A\) and \(B\), \[(a) \: (A \cup B)^c = A^c \cap B^c\quad \mbox{and} \quad (b) \: (A \cap B)^c = A^c \cup B^c\]
(Absorption Laws) For all sets \(A\) and \(B\), \[(a) \: A \cup (A \cap B) = A \quad \mbox{and} \quad (b) \: A \cap (A \cup B ) = A\]
(Complements of \(U\) and \(\emptyset\)) \[(a) \: U^c = \emptyset \quad \mbox{and} \quad (b) \: \emptyset^c = U\]
(Set Difference Law) For all sets \(A\) and \(B\), \[A\setminus B = A \cap B^c\]
2.2.4 Exercises
Middle and high school students often struggle to remember the difference between union and intersection.
- Describe a memory trick to help students remember which symbol goes with which of the two operations.
- Review the definitions of the intersection and union of two sets. What key words separate the two definitions from each other?
- Some students, when first learning the mathematical definition of union, think that the definition excludes objects that are in both sets. These students, when given two sets and asked to find \(A \cup B\) will include the items that are in \(A\) only and \(B\) only. They exclude things in \(A \cap B\). What might be the source of this misconception?
- Define a non-numeric universe and two sets, \(A\) and \(B\), in your universe such that \(A \cap B \neq \emptyset\). Describe, using words, each of the following sets:
- \(A \cup B\)
- \(A \cap B\)
- \(A^{C}\)
Let \(A = \{1, 3, 5, 7, 9\}\), \(B=\{1, 2, 3, 4\}\), and \(C=\{3, 6, 9\}\). List the elements of each of the specified sets.
- \(A \cap B\)
- \(A \cup B\)
- \(A \cup C\)
- \((A\cap B) \cup C\)
- \(A \cap (B \cup C)\)
- \(A \times B\)
- \(B \times (A\cap C)\)
For this exercise, assume that \(\mathbb{R}\) is the universal set. For any natural number, \(n\), define \(n\mathbb{Z} = \{nx \vert x \in \mathbb{Z}\}\). Answer the following as true or false. If false, explain why the statement is not true.
- \((2\mathbb{Z})^C = \{2x+1 \vert x \in \mathbb{Z}\}\)
- \(\mathbb{R}\setminus \mathbb{Z}=\mathbb{Z}^C\)
- \(5\mathbb{Z} \cap \{2x+1 \vert x \in \mathbb{Z}\} = 5\mathbb{Z}\)
- \(5\mathbb{Z} \cap 4\mathbb{Z} = 20\mathbb{Z}\)
- \(2\mathbb{Z}\setminus (4\mathbb{Z} \cup 6\mathbb{Z})= \emptyset\)
- \(3\mathbb{Z}\setminus 2\mathbb{Z}=\{3(2x-1) \vert x\in \mathbb{Z} \textrm{ and } x\geq 0\}\)
Let \(A\) and \(B\) be sets. Prove that \(A\subseteq A\cup B\).
Let \(A\) and \(B\) be sets. Prove that if \(A\subseteq B\), then \(A\cup B=B\).
Prove Theorem 2.3.
Prove Part 2 of Theorem 2.4.
Prove that for sets \(A\) and \(B\), \((A\cap B)^c = A^c \cup B^c\) and \((A\cup B)^c=A^c\cap B^c\)
Write \((A\setminus B)\cup (B\setminus A)\) in terms of just unions, intersections, and complements, then simplify your expression.
Often when doing mathematics, the set you are working with or within is left unstated.
- Under what conditions is it important to be explicit with students about the set you are working within?
- What set do you assume you are working in when:
- You are figuring out how much something will cost?
- You are figuring out what proportion of a pizza to give everyone?
- You are determining what the temperature will be if it is predicted to drop 20 degrees overnight?
Construct an algebraic proof for the given statement. Cite a property from Theorem 2.6 for every step.
For all sets \(A\) and \(B\), \[A \cup (B\setminus A)= A \cup B\]