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

###### Example1.21.

Let $p\text{,}$ $q\text{,}$ $r\text{,}$ and $s$ be integers, where $q$ and $s$ are nonzero. Define $p/q \sim r/s$ if $ps = qr\text{.}$ Clearly $\sim$ is reflexive and symmetric. To show that it is also transitive, suppose that $p/q \sim r/s$ and $r/s \sim t/u\text{,}$ with $q\text{,}$ $s\text{,}$ and $u$ all nonzero. Then $ps = qr$ and $ru = st\text{.}$ Therefore,

\begin{equation*} psu = qru = qst\text{.} \end{equation*}

Since $s \neq 0\text{,}$ $pu = qt\text{.}$ Consequently, $p/q \sim t/u\text{.}$

###### Example1.22.

Suppose that $f$ and $g$ are differentiable functions on ${\mathbb R}\text{.}$ We can define an equivalence relation on such functions by letting $f(x) \sim g(x)$ if $f'(x) = g'(x)\text{.}$ It is clear that $\sim$ is both reflexive and symmetric. To demonstrate transitivity, suppose that $f(x) \sim g(x)$ and $g(x) \sim h(x)\text{.}$ From calculus we know that $f(x) - g(x) = c_1$ and $g(x)- h(x) = c_2\text{,}$ where $c_1$ and $c_2$ are both constants. Hence,

\begin{equation*} f(x) - h(x) = ( f(x) - g(x)) + ( g(x)- h(x)) = c_1 + c_2 \end{equation*}

and $f'(x) - h'(x) = 0\text{.}$ Therefore, $f(x) \sim h(x)\text{.}$

###### Example1.23.

For $(x_1, y_1 )$ and $(x_2, y_2)$ in ${\mathbb R}^2\text{,}$ define $(x_1, y_1 ) \sim (x_2, y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}$ Then $\sim$ is an equivalence relation on ${\mathbb R}^2\text{.}$

###### Example1.24.

Let $A$ and $B$ be $2 \times 2$ matrices with entries in the real numbers. We can define an equivalence relation on the set of $2 \times 2$ matrices, by saying $A \sim B$ if there exists an invertible matrix $P$ such that $PAP^{-1} = B\text{.}$ For example, if

\begin{equation*} A = \begin{pmatrix} 1 & 2 \\ -1 & 1 \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} -18 & 33 \\ -11 & 20 \end{pmatrix}\text{,} \end{equation*}

then $A \sim B$ since $PAP^{-1} = B$ for

\begin{equation*} P = \begin{pmatrix} 2 & 5 \\ 1 & 3 \end{pmatrix}\text{.} \end{equation*}

Let $I$ be the $2 \times 2$ identity matrix; that is,

\begin{equation*} I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\text{.} \end{equation*}

Then $IAI^{-1} = IAI = A\text{;}$ therefore, the relation is reflexive. To show symmetry, suppose that $A \sim B\text{.}$ Then there exists an invertible matrix $P$ such that $PAP^{-1} = B\text{.}$ So

\begin{equation*} A = P^{-1} B P = P^{-1} B (P^{-1})^{-1}\text{.} \end{equation*}

Finally, suppose that $A \sim B$ and $B \sim C\text{.}$ Then there exist invertible matrices $P$ and $Q$ such that $PAP^{-1} = B$ and $QBQ^{-1} = C\text{.}$ Since

\begin{equation*} C = QBQ^{-1} = QPAP^{-1} Q^{-1} = (QP)A(QP)^{-1}\text{,} \end{equation*}

the relation is transitive. Two matrices that are equivalent in this manner are said to be similar.

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.

Suppose there exists an equivalence relation $\sim$ on the set $X\text{.}$ For any $x \in X\text{,}$ the reflexive property shows that $x \in [x]$ and so $[x]$ is nonempty. Clearly $X = \bigcup_{x \in X} [x]\text{.}$ Now let $x, y \in X\text{.}$ We need to show that either $[x] = [y]$ or $[x] \cap [y] = \emptyset\text{.}$ Suppose that the intersection of $[x]$ and $[y]$ is not empty and that $z \in [x] \cap [y]\text{.}$ Then $z \sim x$ and $z \sim y\text{.}$ By symmetry and transitivity $x \sim y\text{;}$ hence, $[x] \subset [y]\text{.}$ Similarly, $[y] \subset [x]$ and so $[x] = [y]\text{.}$ Therefore, any two equivalence classes are either disjoint or exactly the same.

Conversely, suppose that ${\mathcal P} = \{X_i\}$ is a partition of a set $X\text{.}$ Let two elements be equivalent if they are in the same partition. Clearly, the relation is reflexive. If $x$ is in the same partition as $y\text{,}$ then $y$ is in the same partition as $x\text{,}$ so $x \sim y$ implies $y \sim x\text{.}$ Finally, if $x$ is in the same partition as $y$ and $y$ is in the same partition as $z\text{,}$ then $x$ must be in the same partition as $z\text{,}$ and transitivity holds.

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

###### Example1.27.

In the equivalence relation in Example 1.21, two pairs of integers, $(p,q)$ and $(r,s)\text{,}$ are in the same equivalence class when they reduce to the same fraction in its lowest terms.

###### Example1.28.

In the equivalence relation in Example 1.22, two functions $f(x)$ and $g(x)$ are in the same partition when they differ by a constant.

###### Example1.29.

We defined an equivalence class on ${\mathbb R}^2$ by $(x_1, y_1 ) \sim (x_2, y_2)$ if $x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}$ Two pairs of real numbers are in the same partition when they lie on the same circle about the origin.

###### Example1.30.

Let $r$ and $s$ be two integers and suppose that $n \in {\mathbb N}\text{.}$ We say that $r$ is congruent to $s$ modulo $n\text{,}$ or $r$ is congruent to $s$ mod $n\text{,}$ if $r - s$ is evenly divisible by $n\text{;}$ that is, $r - s = nk$ for some $k \in {\mathbb Z}\text{.}$ In this case we write $r \equiv s \pmod{n}\text{.}$ For example, $41 \equiv 17 \pmod{ 8}$ since $41 - 17=24$ is divisible by $8\text{.}$ We claim that congruence modulo $n$ forms an equivalence relation of ${\mathbb Z}\text{.}$ Certainly any integer $r$ is equivalent to itself since $r - r = 0$ is divisible by $n\text{.}$ We will now show that the relation is symmetric. If $r \equiv s \pmod{ n}\text{,}$ then $r - s = -(s -r)$ is divisible by $n\text{.}$ So $s - r$ is divisible by $n$ and $s \equiv r \pmod{ n}\text{.}$ Now suppose that $r \equiv s \pmod{ n}$ and $s \equiv t \pmod{ n}\text{.}$ Then there exist integers $k$ and $l$ such that $r -s = kn$ and $s - t = ln\text{.}$ To show transitivity, it is necessary to prove that $r - t$ is divisible by $n\text{.}$ However,

\begin{equation*} r - t = r - s + s - t = kn + ln = (k + l)n\text{,} \end{equation*}

and so $r - t$ is divisible by $n\text{.}$

If we consider the equivalence relation established by the integers modulo $3\text{,}$ then

\begin{align*} {[0]} & = \{ \ldots, -3, 0, 3, 6, \ldots \},\\ {[1]} & = \{ \ldots, -2, 1, 4, 7, \ldots \},\\ {[2]} & = \{ \ldots, -1, 2, 5, 8, \ldots \}\text{.} \end{align*}

Notice that $[0] \cup [1] \cup [2] = {\mathbb Z}$ and also that the sets are disjoint. The sets $[0]\text{,}$ $[1]\text{,}$ and $[2]$ form a partition of the integers.

The integers modulo $n$ are a very important example in the study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings. In our discussion of the integers modulo $n$ we have actually assumed a result known as the division algorithm, which will be stated and proved in Section 6.1.

###### 1.

Consider the relation $R \subset \Z \times \Z$ that holds of $(x,y)$ precisely when $x-y = 3\text{.}$ Is $R$ an equivalence relation? Not not, what specific properties of an equivalence relation does it not satisfy?

###### 2.

Consider a set $X$ and a partition $\mathcal{P}$ of $X\text{.}$ Is it possible for an element $a \in X$ to belong to two distinct sets of $\mathcal{P}\text{?}$ Briefly explain.

###### 3.

Consider the equivalence realtion established by the integers modulo 5. What does the notation $[4]$ mean? Be as specific as you can.

###### 4.

After reading the section, what questions do you still have? Write at least one well formulated question (even if you think you understand everything).

### ExercisesPractice Problems

###### 1.

Consider all points $(x,y) \in \R \times \R = \R^2$ (that is, all ordered pairs of real numbers; he usual real plane). Define $\sim$ defined by $(x,y) \sim (a,b)$ if and only if $x^2 + y^2 = a^2 + b^2\text{.}$ Prove $\sim$ is an equivalence relation.

Hint

There are three things you must check. Note that since our set is a set of ordered pairs, the properties we are checking will need to relate ordered pairs to other ordered pairs.

###### 2.

Determine whether or not the following relations are equivalence relations on the given set. If the relation is not an equivalence relation, state why it fails to be one.

1. $x \sim y$ in ${\mathbb R}$ if $x \geq y$

2. $m \sim n$ in ${\mathbb Z}$ if $mn > 0$

3. $x \sim y$ in ${\mathbb R}$ if $|x - y| \leq 4$

4. $m \sim n$ in ${\mathbb Z}$ if $m \equiv n \pmod{6}$

Hint

(a) The relation fails to be symmetric. (b) The relation is not reflexive, since $0$ is not equivalent to itself. (c) The relation is not transitive.

###### 3.

Define a relation $\sim$ on ${\mathbb R}^2$ by stating that $(a, b) \sim (c, d)$ if and only if $a^2 + b^2 \leq c^2 + d^2\text{.}$ Show that $\sim$ is reflexive and transitive but not symmetric.

Hint

It is helpful to describe the points geometrically. What does $a^2 + b^2$ describe about the point $(a,b)\text{?}$

###### 4.

For each non-negative real numbers $r\text{,}$ define the set $A_r = \{(x,y) \in \R\times \R \st x^2 + y^2 = r^2\}\text{.}$ Prove that $\{A_r\}$ is a partition. Then say which equivalence relation for which it is the set of equivalence classes.

###### 5.

Consider the relation $\sim$ on $\Z$ defined by $a \sim b$ if and only if $ab \ge 0\text{.}$

1. Prove that $\sim$ is not an equivalence relation. Say specifically what property of equivalence relations fails.

2. Let $[a] = \{b \st a \sim b\}$ (the usual way you would define equivalence classes if $\sim$ were an equivalence relation). This still gives you sets of integers. Explain why this collection of sets is not a partition.

### ExercisesCollected Homework

###### 1.

Define the relation $\sim$ on the real numbers $\R$ by $a \sim b$ if and only if $b-a \in \Z\text{.}$ Prove that $\sim$ is an equivalence relation.

###### 2.

Let $\mathcal L$ be the set of all linear functions $f:\R \to \R\text{.}$ Define $\sim$ on $\mathcal L$ by $f \sim g$ if and only if $f(0) = g(0)\text{.}$

1. Prove that $\sim$ is an equivalence relation.

2. Describe the equivalence classes given by $\sim\text{.}$ In particular, describe $[f]$ for $f(x) = 3x+2\text{.}$

3. For each real number $m\text{,}$ define the set $A_m = \{f \in \mathcal L \st f \text{ has slope } m\}\text{.}$ Prove that the collection $\{A_m \st m \in R\}$ is a partition of $\mathcal L\text{.}$

4. Describe the equivalence relation that corresponds to the partition $\{A_m\}$ from the previous part. In particular, give an example of two functions that are equivalent and two that are not.