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

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

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{.}$

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