In
Section 4.1, we explored some elementary properties of sets, such as element membership, subset relationships, and cardinality. In this section, we explore operations with sets, and common ways of combining sets with other sets. We will establish our results via the
element-chasing method of proving set equality.
Subsection 4.2.1 Union, Intersection, and Equality of Sets
The most basic operations with sets are union and intersection.
Definition 4.2.1.
Let \(A\) and \(B\) be sets. The union of \(A\) and \(B\text{,}\) denoted \(A\cup B\text{,}\) is the set of all elements \(x\) which are in \(A\) or \(B\) (or both):
\begin{equation*}
A\cup B := \setof{x}{x\in A \lor x\in B}.
\end{equation*}
The intersection of \(A\) and \(B\text{,}\) denoted \(A\cap B\text{,}\) is the set of all elements \(x\) which are in both \(A\) and \(B\text{:}\)
\begin{equation*}
A\cap B := \setof{x}{x\in A\land x\in B}.
\end{equation*}
If \(A\cap B = \emptyset\text{,}\) we say \(A\) and \(B\) are disjoint.
Activity 4.2.3.
Let \(A = \set{5,10,15}\text{,}\) \(B = \set{\emptyset, 5, \pi}\text{,}\) \(C = \set{ 2, \pi, -\sqrt{7}, \set{2, - \sqrt{7}}}\text{,}\) and \(D = \set{2, -\sqrt{7}}\text{.}\) Give each of the following sets in roster form.
\(\displaystyle A\cup B\)
\(\displaystyle A\cap B\)
\(\displaystyle B\cap C\)
\(\displaystyle C\cup D\)
\(\displaystyle C\cap D\)
Theorem 4.2.4.
Let \(A\) and \(B\) be sets. Then:
\(\displaystyle A\cup A = A\)
\(\displaystyle A\cap A = A\)
\(\displaystyle A\subseteq (A\cup B)\)
\(\displaystyle (A\cap B)\subseteq A\)
Problem 4.2.5.
For each of the following, find sets \(A\) and \(B\) such that:
Theorem 4.2.6.
Let \(A, B\text{,}\) and \(C\) be sets. Then \(C\subseteq A\cap B\) if and only if \(C\subseteq A\) and \(C\subseteq B\text{.}\)
Given the way set theory has reshaped mathematics over the past 150 years, many mathematical proofs rely on the equality of certain sets. While
Axiom 4.1.7 gives a precise meaning to set equality, we typically verify set equality using a technique sometimes called
element chasing.
Proving Sets are Equal via Element-Chasing.
The typical way to prove that sets
\(A\) and
\(B\) are equal via
Axiom 4.1.7 is to show that
\(A\subseteq B\) and
\(B\subseteq A\text{.}\) We generally do this in two steps: first by letting
\(x\in A\) and demonstrating via mathematics and logical deduction that
\(x\in B\text{,}\) and then letting
\(x\in B\) and demonstrating that
\(x\in A\text{.}\)
Consider the following example.
Theorem 4.2.7.
Let \(A\) and \(B\) be sets. Then \(A\cup B = B \cup A\text{.}\)
Proof.
Let \(x\in A\cup B\text{.}\) Then \(x\in A\) or \(x\in B\text{,}\) so \(x\in B\) or \(x\in A\text{.}\) But this means that \(x\in B\cup A\text{,}\) so \(A\cup B\subseteq B\cup A\text{.}\)
Now suppose \(x\in B\cup A\text{.}\) Then \(x\in B\) or \(x\in A\text{,}\) which means \(x\in A\) or \(x\in B\text{.}\) This means that \(x\in A\cup B\text{,}\) so \(B\cup A\subseteq A\cup B\text{.}\)
Union and intersection obey additional algebraic laws.
Theorem 4.2.8.
Let \(A\) and \(B\) be sets. Then \(A\cap B = B\cap A\text{.}\)
Theorem 4.2.9. The Associative Property.
Let \(A,B\text{,}\) and \(C\) be sets. Then:
Theorem 4.2.10. The Distributive Properties.
Let \(A,B\text{,}\) and \(C\) be sets. Then:
Subsection 4.2.2 Complement and Difference
We next wish to introduce the notion of the complement of a set \(A\text{,}\) which we will denote \(A^c\text{.}\) Informally, \(A^c\) consists of all elements which are not in \(A\text{...}\)but, wait —really? All elements? So if \(A\) simultaneously does not contain a \(5\times 5\) Rubik’s cube and the Lincoln Memorial, then \(A^c\) does?
This is clearly untenable. Until now, we’ve been playing a little fast and loose with one thing: the idea of a larger universe
\(U\) in which our sets live. In mathematics we often consider sets of numbers; if we are interested in a set of integers, the universe might be
\(\Z\) (or maybe
\(\N\) if we know they’re positive). This was implicit in our definition of the set
\(B\) in
Example 4.1.4, as the first half of the set-builder form specified that we were considering only
\(x\in \Z\text{.}\)
This universe is typically implied (as it was in
Example 4.1.4), but in defining and using both the complement and relative complement (the set difference), our definitions and theorems will name the universal set
\(U\text{.}\)
Definition 4.2.11.
Let \(A\) be a set contained in some universe \(U\text{.}\) Then the complement of \(A\), denoted \(A^c\text{,}\) is the set of elements \(x\in U\) with \(x\notin A\text{.}\) That is:
\begin{equation*}
A^c := \setof{x\in U}{x\notin A}.
\end{equation*}
Activity 4.2.12.
Consider \(A = \set{-2,-1,0,1,2}\) and \(B = \set{0,3}\) in the universe \(U = \set{-4,-3,-2,-1,0,1,2,3}\text{.}\) Calculate:
\(A^c\text{.}\)
\(B^c\text{.}\)
\(\displaystyle (A\cap B)^c\)
\(\displaystyle A^c \cup B^c\)
\(\displaystyle (A\cup B)^c\)
\(\displaystyle A^c \cap B^c\)
Theorem 4.2.13.
Let \(A\) be a set in a universe \(U\text{.}\) Then \(A\cup A^c = U\text{.}\)
Theorem 4.2.14.
Let \(A\) be a set in a universe \(U\text{.}\) Then \(A\cap A^c = \emptyset\text{.}\)
Theorem 4.2.15.
Let \(A\) be a set in a universe \(U\text{.}\) Then \((A^c)^c = A\text{.}\)
Theorem 4.2.16.
Let \(A,B\) be subsets of some shared universe \(U\text{.}\) Then:
\(\displaystyle (A\cup B)^c = A^c \cap B^c\)
\(\displaystyle (A\cap B)^c = A^c \cup B^c\)
Theorem 4.2.17.
Let \(A\) and \(B\) be subsets of a shared universe \(U\text{.}\) Then \(A\subseteq B\) if and only if \(B^c\subseteq A^c\text{.}\)
Another important set operation related to the complement is the set difference.
Definition 4.2.18.
Let \(A\) and \(B\) be sets. The (set) difference of \(A\) and \(B\) (sometimes called the relative complement of \(A\) in \(B\)), denoted \(A\setminus B\text{,}\) is the set of elements \(x\) such that \(x\in A\) and \(x\notin B\text{:}\)
\begin{equation*}
A\setminus B := \setof{x}{x\in A \land x\notin B}.
\end{equation*}
Problem 4.2.19.
Let \(A\) and \(B\) be sets. Give a proof or counterexample of the following:
\begin{equation*}
A\setminus B = B\setminus A.
\end{equation*}
Theorem 4.2.20.
Let \(A\) and \(B\) be sets. Then \(A = (A\setminus B) \cup (A\cap B)\text{.}\)
Theorem 4.2.21.
Let \(A\) and \(B\) be sets. Then
\begin{equation*}
A\setminus (A\setminus B) = A\cap B.
\end{equation*}
Problem 4.2.22.
Let \(A, B\text{,}\) and \(C\) be sets. Prove or give a counterexample that
\begin{equation*}
A\setminus (B\setminus C) = (A\setminus B) \cup (A\cap C).
\end{equation*}
Subsection 4.2.3 Cartesian Products
The last significant operation we’ll do on sets is, in some sense, multiply them.
Definition 4.2.23.
Let \(A, B\) be sets. Given elements \(a\in A\) and \(b\in B\text{,}\) the ordered pair \((a,b)\) is the set
\begin{equation*}
(a,b) := \set{\set{a}, \set{a,b}}.
\end{equation*}
The Cartesian product of \(A\) and \(B\text{,}\) denoted \(A\times B\text{,}\) is the set of all ordered pairs whose first coordinate is from \(A\) and whose second coordinate is from \(B\text{:}\)
\begin{equation*}
A\times B := \setof{(a,b)}{a\in A, \ b\in B}.
\end{equation*}
We include the definition of ordered pairs in
Definition 4.2.23 for completeness, but in practice we rarely use it, instead relying on our intuition for how ordered pairs work in the
\(xy\)-plane,
\(\R\times \R\text{.}\)
It is standard to denote the product of a set \(A\) with itself as \(A^2\text{,}\) \(A\times A \times A = A^3\text{,}\) and so on.
Problem 4.2.25.
Given the definition of ordered pair in
Definition 4.2.23 and
\((1,2), (2,1)\in \Z\times \Z\text{,}\) is it true that
\((1,2) = (2,1)\text{?}\)
Activity 4.2.26.
Let \(A = \set{5,10,15}\text{,}\) \(B = \set{\emptyset, 5, \pi}\text{,}\) \(C = \set{ 2, \pi, -\sqrt{7}, \set{2, - \sqrt{7}}}\text{,}\) and \(D = \set{2, -\sqrt{7}}\text{.}\)
List three elements of \(C\times D\text{.}\)
How many elements are in \(A\times B\text{?}\) How about \(B\times D\text{?}\)
Describe \(A\times\emptyset\text{.}\)
Let \(S,T\) be sets with \(|S| = m\) and \(|T| = n\text{.}\) Conjecture a formula for \(|S\times T|\text{,}\) and then prove your formula is correct.
We conclude this section with an exploration of some set-theoretic identities involving the Cartesian product.
Theorem 4.2.27.
Let \(A, B, C, D\) be sets with \(A\subseteq B\) and \(C\subseteq D\text{.}\) Then \(A\times C\subseteq B\times D\text{.}\)
Theorem 4.2.28.
Let \(A,B, C\) be sets. Then
\begin{equation*}
(A\cup B)\times C = (A\times C) \cup (B\times C).
\end{equation*}
Theorem 4.2.29.
Let \(A,B,C\) be sets. Then
\begin{equation*}
A\times (B\setminus C) = (A\times B)\setminus (A\times C).
\end{equation*}
