Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \setcounter{chapter}{-1}\)

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*}


\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*}


\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*}

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*}


\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*}

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*}


\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{.}\)

(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.


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*}