##
Subsection5.1Set Theory

ΒΆA **set** is a well-defined collection of objects; that is, it is defined in such a manner that we can determine for any given object \(x\) whether or not \(x\) belongs to the set. The objects that belong to a set are called its **elements** or **members**. We will denote sets by capital letters, such as \(A\) or \(X\text{;}\) if \(a\) is an element of the set \(A\text{,}\) we write \(a \in A\text{.}\)

A set is usually specified either by listing all of its elements inside a pair of braces or by stating the property that determines whether or not an object \(x\) belongs to the set. We might write

\begin{equation*}
X = \{ x_1, x_2, \ldots, x_n \}
\end{equation*}
for a set containing elements \(x_1, x_2, \ldots, x_n\) or

\begin{equation*}
X = \{ x :x \text{ satisfies }{\mathcal P}\}
\end{equation*}
if each \(x\) in \(X\) satisfies a certain property \({\mathcal P}\text{.}\) For example, if \(E\) is the set of even positive integers, we can describe \(E\) by writing either

\begin{equation*}
E = \{2, 4, 6, \ldots \} \quad \text{or} \quad E = \{ x : x \text{ is an even integer and } x \gt 0 \}.
\end{equation*}
We write \(2 \in E\) when we want to say that 2 is in the set \(E\text{,}\) and \(-3 \notin E\) to say that \(-3\) is not in the set \(E\text{.}\)

Some of the more important sets that we will consider are the following:

\begin{gather*}
{\mathbb N} = \{n: n \text{ is a natural number}\} = \{1, 2, 3, \ldots \};\\
{\mathbb Z} = \{n : n \text{ is an integer} \} = \{\ldots, -1, 0, 1, 2, \ldots \};\\
{\mathbb Q} = \{r : r \text{ is a rational number}\} = \{p/q : p, q \in {\mathbb Z} \text{ where } q \neq 0\};\\
{\mathbb R} = \{ x : x \text{ is a real number} \};\\
{\mathbb C} = \{z : z \text{ is a complex number}\}.
\end{gather*}
We can find various relations between sets as well as perform operations on sets. A set \(A\) is a **subset** of \(B\text{,}\) written \(A \subset B\) or \(B \supset A\text{,}\) if every element of \(A\) is also an element of \(B\text{.}\) For example,

\begin{equation*}
\{4,5,8\} \subset \{2, 3, 4, 5, 6, 7, 8, 9 \}
\end{equation*}
and

\begin{equation*}
{\mathbb N} \subset {\mathbb Z} \subset {\mathbb Q} \subset {\mathbb R} \subset {\mathbb C}.
\end{equation*}
Trivially, every set is a subset of itself. A set \(B\) is a **proper subset** of a set \(A\) if \(B \subset A\) but \(B \neq A\text{.}\) If \(A\) is not a subset of \(B\text{,}\) we write \(A \notsubset B\text{;}\) for example, \(\{4, 7, 9\} \notsubset \{2, 4, 5, 8, 9 \}\text{.}\) Two sets are **equal**, written \(A = B\text{,}\) if we can show that \(A \subset B\) and \(B \subset A\text{.}\)

It is convenient to have a set with no elements in it. This set is called the **empty set** and is denoted by \(\emptyset\text{.}\) Note that the empty set is a subset of every set.

To construct new sets out of old sets, we can perform certain operations: the **union** \(A \cup B\) of two sets \(A\) and \(B\) is defined as

\begin{equation*}
A \cup B = \{x : x \in A \text{ or } x \in B \};
\end{equation*}
the **intersection** of \(A\) and \(B\) is defined by

\begin{equation*}
A \cap B = \{x : x \in A \text{ and } x \in B \}.
\end{equation*}
If \(A = \{1, 3, 5\}\) and \(B = \{ 1, 2, 3, 9 \}\text{,}\) then

\begin{equation*}
A \cup B = \{1, 2, 3, 5, 9 \} \quad \text{and} \quad A \cap B = \{ 1, 3 \}.
\end{equation*}
We can consider the union and the intersection of more than two sets. In this case we write

\begin{equation*}
\bigcup_{i = 1}^{n} A_{i} = A_{1} \cup \ldots \cup A_n
\end{equation*}
and

\begin{equation*}
\bigcap_{i = 1}^{n} A_{i} = A_{1} \cap \ldots \cap A_n
\end{equation*}
for the union and intersection, respectively, of the sets \(A_1, \ldots, A_n\text{.}\)

When two sets have no elements in common, they are said to be **disjoint**; for example, if \(E\) is the set of even integers and \(O\) is the set of odd integers, then \(E\) and \(O\) are disjoint. Two sets \(A\) and \(B\) are disjoint exactly when \(A \cap B = \emptyset\text{.}\)

Sometimes we will work within one fixed set \(U\text{,}\) called the **universal set**. For any set \(A \subset U\text{,}\) we define the **complement** of \(A\text{,}\) denoted by \(A'\text{,}\) to be the set

\begin{equation*}
A' = \{ x : x \in U \text{ and } x \notin A \}.
\end{equation*}
We define the **difference** of two sets \(A\) and \(B\) to be

\begin{equation*}
A \setminus B = A \cap B' = \{ x : x \in A \text{ and } x \notin B \}.
\end{equation*}
######
Example5.1

Let \({\mathbb R}\) be the universal set and suppose that

\begin{equation*}
A = \{ x \in {\mathbb R} : 0 \lt x \leq 3 \} \quad \text{and} \quad B = \{ x \in {\mathbb R} : 2 \leq x \lt 4 \}.
\end{equation*}
Then

\begin{align*}
A \cap B & = \{ x \in {\mathbb R} : 2 \leq x \leq 3 \}\\
A \cup B & = \{ x \in {\mathbb R} : 0 \lt x \lt 4 \}\\
A \setminus B & = \{ x \in {\mathbb R} : 0 \lt x \lt 2 \}\\
A' & = \{ x \in {\mathbb R} : x \leq 0 \text{ or } x \gt 3 \}.
\end{align*}
######
Proposition5.2

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets. Then

\(A \cup A = A\text{,}\) \(A \cap A = A\text{,}\) and \(A \setminus A = \emptyset\text{;}\)

\(A \cup \emptyset = A\) and \(A \cap \emptyset = \emptyset\text{;}\)

\(A \cup (B \cup C) = (A \cup B) \cup C\) and \(A \cap (B \cap C) = (A \cap B) \cap C\text{;}\)

\(A \cup B = B \cup A\) and \(A \cap B = B \cap A\text{;}\)

\(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\text{;}\)

\(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\text{.}\)

We will prove (1) and (3) and leave the remaining results to be proven in the exercises.

(1) Observe that

\begin{align*}
A \cup A & = \{ x : x \in A \text{ or } x \in A \}\\
& = \{ x : x \in A \}\\
& = A
\end{align*}
and

\begin{align*}
A \cap A & = \{ x : x \in A \text{ and } x \in A \}\\
& = \{ x : x \in A \}\\
& = A.
\end{align*}
Also, \(A \setminus A = A \cap A' = \emptyset\text{.}\)

(3) For sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\)

\begin{align*}
A \cup (B \cup C) & = A \cup \{ x : x \in B \text{ or } x \in C \}\\
& = \{ x : x \in A \text{ or } x \in B, \text{ or } x \in C \}\\
& = \{ x : x \in A \text{ or } x \in B \} \cup C\\
& = (A \cup B) \cup C.
\end{align*}
A similar argument proves that \(A \cap (B \cap C) = (A \cap B) \cap C\text{.}\)

######
Theorem5.3De Morgan's Laws

Let \(A\) and \(B\) be sets. Then

\((A \cup B)' = A' \cap B'\text{;}\)

\((A \cap B)' = A' \cup B'\text{.}\)

(1) If \(A \cup B = \emptyset\text{,}\) then the theorem follows immediately since both \(A\) and \(B\) are the empty set. Otherwise, we must show that \((A \cup B)' \subset A' \cap B'\) and \((A \cup B)' \supset A' \cap B'\text{.}\) Let \(x \in (A \cup B)'\text{.}\) Then \(x \notin A \cup B\text{.}\) So \(x\) is neither in \(A\) nor in \(B\text{,}\) by the definition of the union of sets. By the definition of the complement, \(x \in A'\) and \(x \in B'\text{.}\) Therefore, \(x \in A' \cap B'\) and we have \((A \cup B)' \subset A' \cap B'\text{.}\)

To show the reverse inclusion, suppose that \(x \in A' \cap B'\text{.}\) Then \(x \in A'\) and \(x \in B'\text{,}\) and so \(x \notin A\) and \(x \notin B\text{.}\) Thus \(x \notin A \cup B\) and so \(x \in (A \cup B)'\text{.}\) Hence, \((A \cup B)' \supset A' \cap B'\) and so \((A \cup B)' = A' \cap B'\text{.}\)

The proof of (2) is left as an exercise.

######
Example5.4

Other relations between sets often hold true. For example,

\begin{equation*}
( A \setminus B) \cap (B \setminus A) = \emptyset.
\end{equation*}
To see that this is true, observe that

\begin{align*}
( A \setminus B) \cap (B \setminus A) & = ( A \cap B') \cap (B \cap A')\\
& = A \cap A' \cap B \cap B'\\
& = \emptyset.
\end{align*}