# Subsection1.2.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{align*} {\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{align*}

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

# Subsection1.2.2Cartesian Products and Mappings

Given sets $A$ and $B\text{,}$ we can define a new set $A \times B\text{,}$ called the Cartesian product of $A$ and $B\text{,}$ as a set of ordered pairs. That is,

\begin{equation*} A \times B = \{ (a,b) : a \in A \text{ and } b \in B \}. \end{equation*}

We define the Cartesian product of $n$ sets to be

\begin{equation*} A_1 \times \cdots \times A_n = \{ (a_1, \ldots, a_n): a_i \in A_i \text{ for } i = 1, \ldots, n \}. \end{equation*}

If $A = A_1 = A_2 = \cdots = A_n\text{,}$ we often write $A^n$ for $A \times \cdots \times A$ (where $A$ would be written $n$ times). For example, the set ${\mathbb R}^3$ consists of all of 3-tuples of real numbers.

Subsets of $A \times B$ are called relations. We will define a mapping or function $f \subset A \times B$ from a set $A$ to a set $B$ to be the special type of relation where $(a, b) \in f$ if for every element $a \in A$ there exists a unique element $b \in B\text{.}$ Another way of saying this is that for every element in $A\text{,}$ $f$ assigns a unique element in $B\text{.}$ We usually write $f:A \rightarrow B$ or $A \stackrel{f}{\rightarrow} B\text{.}$ Instead of writing down ordered pairs $(a,b) \in A \times B\text{,}$ we write $f(a) = b$ or $f : a \mapsto b\text{.}$ The set $A$ is called the domain of $f$ and

\begin{equation*} f(A) = \{ f(a) : a \in A \} \subset B \end{equation*}

is called the range or image of $f\text{.}$ We can think of the elements in the function's domain as input values and the elements in the function's range as output values.

Given a function $f : A \rightarrow B\text{,}$ it is often possible to write a list describing what the function does to each specific element in the domain. However, not all functions can be described in this manner. For example, the function $f: {\mathbb R} \rightarrow {\mathbb R}$ that sends each real number to its cube is a mapping that must be described by writing $f(x) = x^3$ or $f:x \mapsto x^3\text{.}$

Consider the relation $f : {\mathbb Q} \rightarrow {\mathbb Z}$ given by $f(p/q) = p\text{.}$ We know that $1/2 = 2/4\text{,}$ but is $f(1/2) = 1$ or 2? This relation cannot be a mapping because it is not well-defined. A relation is well-defined if each element in the domain is assigned to a unique element in the range.

If $f:A \rightarrow B$ is a map and the image of $f$ is $B\text{,}$ i.e., $f(A) = B\text{,}$ then $f$ is said to be onto or surjective. In other words, if there exists an $a \in A$ for each $b \in B$ such that $f(a) = b\text{,}$ then $f$ is onto. A map is one-to-one or injective if $a_1 \neq a_2$ implies $f(a_1) \neq f(a_2)\text{.}$ Equivalently, a function is one-to-one if $f(a_1) = f(a_2)$ implies $a_1 = a_2\text{.}$ A map that is both one-to-one and onto is called bijective.

Given two functions, we can construct a new function by using the range of the first function as the domain of the second function. Let $f : A \rightarrow B$ and $g : B \rightarrow C$ be mappings. Define a new map, the composition of $f$ and $g$ from $A$ to $C\text{,}$ by $(g \circ f)(x) = g(f(x))\text{.}$

##### Proof

If $S$ is any set, we will use $id_S$ or $id$ to denote the identity mapping from $S$ to itself. Define this map by $id(s) = s$ for all $s \in S\text{.}$ A map $g: B \rightarrow A$ is an inverse mapping of $f: A \rightarrow B$ if $g \circ f = id_A$ and $f \circ g = id_B\text{;}$ in other words, the inverse function of a function simply “undoes” the function. A map is said to be invertible if it has an inverse. We usually write $f^{-1}$ for the inverse of $f\text{.}$

# Subsection1.2.3Equivalence Relations and Partitions

A fundamental notion in mathematics is that of equality. We can generalize equality with equivalence relations and equivalence classes. An equivalence relation on a set $X$ is a relation $R \subset X \times X$ such that

• $(x, x) \in R$ for all $x \in X$ (reflexive property);

• $(x, y) \in R$ implies $(y, x) \in R$ (symmetric property);

• $(x, y)$ and $(y, z) \in R$ imply $(x, z) \in R$ (transitive property).

Given an equivalence relation $R$ on a set $X\text{,}$ we usually write $x \sim y$ instead of $(x, y) \in R\text{.}$ If the equivalence relation already has an associated notation such as $=\text{,}$ $\equiv\text{,}$ or $\cong\text{,}$ we will use that notation.

A partition ${\mathcal P}$ of a set $X$ is a collection of nonempty sets $X_1, X_2, \ldots$ such that $X_i \cap X_j = \emptyset$ for $i \neq j$ and $\bigcup_k X_k = X\text{.}$ Let $\sim$ be an equivalence relation on a set $X$ and let $x \in X\text{.}$ Then $[x] = \{ y \in X : y \sim x \}$ is called the equivalence class of $x\text{.}$ We will see that an equivalence relation gives rise to a partition via equivalence classes. Also, whenever a partition of a set exists, there is some natural underlying equivalence relation, as the following theorem demonstrates.

##### Proof

Let us examine some of the partitions given by the equivalence classes in the last set of examples.