# Section1.2Sets and Equivalence Relations¶ permalink

# 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,

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

the *intersection* of \(A\) and \(B\) is defined by

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

We define the *difference* of two sets \(A\) and \(B\) to be

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

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

# 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,

We define the *Cartesian product of \(n\) sets* to be

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

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

##### Theorem1.2.15

Let \(f : A \rightarrow B\text{,}\) \(g : B \rightarrow C\text{,}\) and \(h : C \rightarrow D\text{.}\) Then

The composition of mappings is associative; that is, \((h \circ g) \circ f = h \circ (g \circ f)\text{;}\)

If \(f\) and \(g\) are both one-to-one, then the mapping \(g \circ f\) is one-to-one;

If \(f\) and \(g\) are both onto, then the mapping \(g \circ f\) is onto;

If \(f\) and \(g\) are bijective, then so is \(g \circ f\text{.}\)

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

##### Theorem1.2.20

A mapping is invertible if and only if it is both one-to-one and onto.

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

##### Theorem1.2.25

Given an equivalence relation \(\sim\) on a set \(X\text{,}\) the equivalence classes of \(X\) form a partition of \(X\text{.}\) Conversely, if \({\mathcal P} = \{ X_i\}\) is a partition of a set \(X\text{,}\) then there is an equivalence relation on \(X\) with equivalence classes \(X_i\text{.}\)

##### Corollary1.2.26

Two equivalence classes of an equivalence relation are either disjoint or equal.

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