### Definition of an Equivalence Relation

A binary relation on a non-empty set \(A\) is said to be an equivalence relation if and only if the relation is

- reflexive
- symmetric, and
- transitive.

Two elements \(a\) and \(b\) related by an equivalent relation are called equivalent elements and generally denoted as \(a \sim b\) or \(a\equiv b.\) For an equivalence relation \(R\), you can also see the following notations: \(a \sim_R b,\) \(a \equiv_R b.\)

The equivalence relation is a key mathematical concept that generalizes the notion of equality. It provides a formal way for specifying whether or not two quantities are the same with respect to a given setting or an attribute.

Examples of Equivalence Relations

#### Equality Relation

The equality relation between real numbers or sets, denoted by \(=,\) is the canonical example of an equivalence relation.

The equality relation \(R\) on the set of real numbers is defined by

\[R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{R}, b \in \mathbb{R}, a = b} \,\right\}.\]

\(R\) is reflexive since every real number equals itself: \(a = a.\)

\(R\) is symmetric: if \(a = b\) then \(b = a.\)

The relation \(R\) is transitive: if \(a = b\) and \(b = c,\) then we get

\[{\left\{ \begin{array}{l} a = b\\ b = c \end{array} \right.,}\;\; \Rightarrow {a = b = c,}\;\; \Rightarrow {a = c.}\]

#### Parity Relation

Two numbers are said to have the same parity if they are both even or both odd. Consider the set of integers and define a relation \(R:\)

\[{R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{Z}, b \in \mathbb{Z},}\right.}\kern0pt{\left.{ a \text{ and } b \text{ have the same parity}} \right\}.}\]

The parity relation \(R\) is an equivalence relation.

\(R\) is reflexive as, for any \(a \in \mathbb{Z},\) the number \(a\) has the same parity as itself: \(\left( {a,a} \right) \in R.\)

\(R\) is symmetric. If \(\left( {a,b} \right) \in R,\) and therefore both \(a\) and \(b\) have the same parity, then we can write \(\left( {b,a} \right) \in R.\)

The relation \(R\) is transitive. If \(\left( {a,b} \right) \in R\) and \(\left( {b,c} \right) \in R,\) then all three numbers \(a, b,\) and \(c\) have the same parity, so \(\left( {a,c} \right) \in R.\)

#### Congruence Modulo \(n\)

Let \(n\) be a non-zero integer. The numbers \(a,b \in \mathbb{Z}\) are said to be congruent modulo \(n\) if \(n \mid \left( {a – b} \right),\) that is \(n\) divides \(\left( {a – b} \right).\) This is written as

\[a \equiv b \;\left( \kern-2pt{\bmod n} \right).\]

For example,

\[7 \equiv 12 \;\left( \kern-2pt{\bmod 5} \right).\]

Congruence modulo \(n\) is an equivalence relation. Let

\[{R = \left\{ {\left( {a,b} \right) \mid a \in \mathbb{Z}, b \in \mathbb{Z},}\right.}\kern0pt{\left.{ a \equiv b\;\left( \kern-2pt{\bmod n} \right)} \right\}.}\]

\(R\) is reflexive since \(a – a = 0\) is a multiple of any \(n.\)

\(R\) is symmetric. If \(a \equiv b\;\left( \kern-2pt{\bmod n}\right),\) then \(a – b = n\cdot k,\) where \(k\) is an integer. Hence, \(b – a = n\cdot \left({-k}\right),\) where \(-k\) is also an integer. So we have \(b \equiv a\;\left( \kern-2pt{\bmod n}\right).\)

The relation \(R\) is transitive. Suppose that \(a \equiv b\;\left( \kern-2pt{\bmod n}\right)\) and \(b \equiv c\;\left( \kern-2pt{\bmod n}\right).\) We can write these equations as

\[{a – b = n \cdot k \;\text{ and }\;}\kern0pt{ b – c = n \cdot \ell,}\]

where \(k, \ell\) are some integers.

By adding these together, we have

\[{\left( {a – c} \right) }={ \left( {a – b} \right) + \left( {b – c} \right) }={ n \cdot k + n \cdot l }={ n\left( {k + l} \right).}\]

Since \(k\) and \(\ell\) are integers, then their sum \(k + \ell\) is also an integer. It follows from here that \(a \equiv c\;\left( \kern-2pt{\bmod n}\right).\) This proves the transitivity of \(R.\)

Note that congruence modulo \(n\) for \(n = 2\) is also called the parity relation considered above.

#### Some Other Examples

The following relations are equivalence relations:

- “\(a\) and \(b\) live in the same city” on the set of all people;
- “\(a\) and \(b\) are the same age” on the set of all people;
- “\(a\) and \(b\) were born in the same month” on the set of all people;
- “\(a\) and \(b\) have the same remainder when divided by \(3\)” on the set of integers;
- “\(a\) and \(b\) have the same last digit” on the set of integers;

Any relation that can be defined using expressions like “have the same” or “are the same” is an equivalence relation. - “\(a\) and \(b\) are parallel lines” on the set of all straight lines of a plane;
- “\(a\) and \(b\) are similar triangles” on the set of all triangles;
- Two functions \(f\left( x \right)\) and \(g\left( x \right),\) where \(x \in \mathbb{R},\) are said to be equivalent as \(x \to {x_0},\) if \[\lim\limits_{x \to {x_0}} \frac{{f\left( x \right)}}{{g\left( x \right)}} = 1,\] provided \({g\left( x \right)} \ne 0\) at \(x = {x_0}.\) For example, \(\sin x \sim x\) as \(x \to 0.\)

### Equivalence Relation Closure

Let \(R\) be an arbitrary binary relation on a non-empty set \(A.\) To turn \(R\) into an equivalence relation, we can take the reflexive, symmetric, and transitive closures of \(R.\) This triple operation is denoted by \(tsr\left(R\right).\)

\(tsr\left(R\right)\) is the the smallest equivalence relation that contains \(R.\) The order of taking symmetric and transitive closures is essential. One can show, for example, that \(str\left(R\right)\) need not be an equivalence relation.

The equivalence relation \(tsr\left(R\right)\) can be calculated by the formula

\[{tsr\left( R \right) }={ t\left( {s\left( {r\left( R \right)} \right)} \right) }={ {\left( {R \cup I \cup {R^{ – 1}}} \right)^*},}\]

where the asterisk symbol denotes the connectivity relation.

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Which of these relations on the set \(A = \left\{ {1,2,3,4} \right\}\) are equivalence relations?- \({R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.\)
- \({R_2} = \left\{ {\left( {1,4} \right),\left( {2,2} \right),\left( {3,3} \right),\left( {4,1} \right),} \right.\) \(\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.\)
- \({R_3} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),\left( {3,2} \right)} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {4,4} \right)} \right\}\)
- \({R_4} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,1} \right),\left( {4,4} \right)} \right\}.\)

### Example 2

Which of these relations on the set of all people are equivalence relations?- \(a\) and \(b\) speak the same language.
- \(a\) and \(b\) speak a common language.
- \(a\) and \(b\) have the same mother.
- \(a\) lives within \(5\) miles of \(b.\)
- \(a\) loves \(b.\)
- \(a\) and \(b\) are younger than \(20.\)
- \(a\) is older than \(b.\)

### Example 3

Determine whether the relation \(R\) given by the digraph is an equivalence relation.### Example 4

Determine whether the relation \(S\) given by the digraph is an equivalence relation.### Example 5

The relation \(R\) on the set of real numbers \(\mathbb{R}\) is given by \[R = \left\{ {\left( {a,b} \right) \mid a – b \in \mathbb{Z}} \right\}.\] Determine whether it is an equivalence relation.### Example 6

The relation \(S\) on the set of integers \(\mathbb{Z}\) is given by \[{S = \left\{ {\left( {a,b} \right), \left( {c,d} \right) \mid ad = bc,}\right.}\kern0pt{\left.{ b \ne 0, d \ne 0} \right\}.}\] Determine whether it is an equivalence relation.### Example 7

A binary relation \(R\) is given by the matrix \[{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&0&0&0\\ 0&0&0&1\\ 0&0&0&1 \end{array}} \right].\] Determine the equivalence relation closure of \(R.\)### Example 1.

Which of these relations on the set \(A = \left\{ {1,2,3,4} \right\}\) are equivalence relations?- \({R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.\)
- \({R_2} = \left\{ {\left( {1,4} \right),\left( {2,2} \right),\left( {3,3} \right),\left( {4,1} \right),} \right.\) \(\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.\)
- \({R_3} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),\left( {3,2} \right)} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {4,4} \right)} \right\}\)
- \({R_4} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,1} \right),\left( {4,4} \right)} \right\}.\)

Solution.

- \(R_1\) is an equivalence relation since it is reflexive, symmetric, and transitive.
- \(R_2\) is not reflexive since \({\left( {1,1} \right)} \notin {R_2}.\) \(R_2\) is not symmetric because \({\left( {4,2} \right)} \in {R_2},\) but \({\left( {2,4} \right)} \notin {R_2}.\) \(R_2\) is not transitive: \({\left( {1,4} \right), \left( {4,2} \right)} \in {R_2},\) but \({\left( {1,4} \right)} \notin {R_2}.\) Hence, \(R_2\) is not an equivalence relation.
- \(R_3\) is an equivalence relation since it is reflexive, symmetric, and transitive.
- \(R_4\) is not symmetric since \({\left( {1,2} \right)} \in {R_4},\) but \({\left( {2,1} \right)} \notin {R_4}.\) Similarly \({\left( {2,4} \right)} \in {R_4},\) but \({\left( {4,2} \right)} \notin {R_4}.\) Thus \(R_4\) is not an equivalence relation.

### Example 2.

Which of these relations on the set of all people are equivalence relations?- \(a\) and \(b\) speak the same language.
- \(a\) and \(b\) speak a common language.
- \(a\) and \(b\) have the same mother.
- \(a\) lives within \(5\) miles of \(b.\)
- \(a\) loves \(b.\)
- \(a\) and \(b\) are younger than \(20.\)
- \(a\) is older than \(b.\)

Solution.

- Obviously, \(a\) speaks the same language, so this relation is reflexive. If \(a\) speaks the same language as \(b,\) then \(b\) speaks the same language as \(a,\) so this relation is symmetric. If \(a\) speaks the same language as \(b\) and \(b\) speaks the same language as \(c,\) then \(a\) speaks the same language as \(c.\) Thus, this relation is transitive. We see that the relation satisfies all three properties. Hence, this is an equivalence relation.
- This relation is reflexive and symmetric, but not transitive. For example, \(a\) and \(b\) speak a common language, say French, and \(b\) and \(c\) speak another common language, say German. This means that \(a\) and \(c\) may not have a common language. Therefore, the relation is not an equivalence relation.
- This is an equivalence relation because it is reflexive, symmetric, and transitive.
- This relation is reflexive and symmetric, but it is not transitive. As a counterexample, consider the case when \(a,\) \(b,\) and \(c\) are located on the same straight line. If the distance between \(a\) and \(b\) is \(5\) miles, and the distance between \(b\) and \(c\) is also \(5\) miles, the distance between \(a\) and \(c\) may be equal to \(10\) miles. Thus, this is not an equivalence relation.
- This relation is not reflexive. Though many people love themselves, this does not mean that this property is true for all people in the relation. Similarly, if \(a\) loves \(b,\) then it may be that \(b\) loves \(a,\) but it may also not be. So, the relation is not symmetric. It is easy to see that the relation is not transitive. If Paul loves Amy but Amy loves Nick, then it is unlikely that Paul loves Nick. Hence, this relation is not transitive. Thus we see that the given relation is not an equivalence relation.
- This relation is reflexive, symmetric, and transitive. Therefore, this is an equivalence relation.
- This relation is not reflexive: \(a\) as not older than itself. This relation is not symmetric: If \(a\) is older than \(b,\) than the converse is false. This relation is transitive: if \(a\) is older than \(b\) and \(b\) is older than \(c,\) then \(a\) is older than \(c.\) Given these properties, we conclude that this is not an equivalence relation.

### Example 3.

Determine whether the relation \(R\) given by the digraph is an equivalence relation.Solution.

The relation \(R\) is reflexive and transitive, but it is not symmetric: \(\left( {2,3} \right) \in R,\) but \(\left( {3,2} \right) \notin R.\) Similarly two other edges \(\left( {2,4} \right)\) and \(\left( {4,2} \right).\) Hence, the relation \(R\) is not an equivalence relation. The missing edges are marked in red.

### Example 4.

Determine whether the relation \(S\) given by the digraph is an equivalence relation.Solution.

The relation \(S\) is not reflexive because the element \(\left( {5,5} \right)\) is missing. Thus, \(S\) is not an equivalence relation. We can build the equivalence closure of \(S\) by adding a self-loop to the node \(5\) on the digraph:

### Example 5.

The relation \(R\) on the set of real numbers \(\mathbb{R}\) is given by \[R = \left\{ {\left( {a,b} \right) \mid a – b \in \mathbb{Z}} \right\}.\] Determine whether it is an equivalence relation.Solution.

Obviously, \(R\) is reflexive since \(a – a = 0 \in \mathbb{Z}.\)

\(R\) is symmetric: if \(\left( {a,b} \right) \in R\) and hence \({a – b = n \in \mathbb{Z}},\) then \(b – a = -n\) is also an integer, so we have \(\left( {b,a} \right) \in R.\)

\(R\) is transitive. Indeed, let \(\left( {a,b} \right) \in R\) and \(\left( {b,c} \right) \in R.\) Then \(a – b = n\) and \(b – c = m,\) where \(n, m\) are certain integers. By adding the two equations, we obtain

\[{\left\{ \begin{array}{l} a – b = n\\ b – c = m \end{array} \right.,}\;\; \Rightarrow {\left( {a – b} \right) + \left( {b – c} \right) = n + m,}\;\; \Rightarrow {a – c = n + m,}\]

where \(n + m \in \mathbb{Z}.\) This proves the transitivity of \(R.\)

Thus, the relation \(R\) is an equivalence relation.

### Example 6.

The relation \(S\) on the set of integers \(\mathbb{Z}\) is given by \[{S = \left\{ {\left( {a,b} \right), \left( {c,d} \right) \mid ad = bc,}\right.}\kern0pt{\left.{ b \ne 0, d \ne 0} \right\}.}\] Determine whether it is an equivalence relation.Solution.

The relation \(S\) is reflexive. Indeed, \(\left( {a,b} \right)S\left( {a,b} \right)\) is given by

\[{ab = ba,}\;\; \Rightarrow {ab = ab.}\]

The relation \(S\) is symmetric because \(\left( {c,d} \right)S\left( {a,b} \right)\) means that

\[{cb = da,}\;\; \Rightarrow {ad = bc.}\]

Check \(S\) for the transitivity property. Since \(\left( {a,b} \right)S\left( {c,d} \right)\) and \(\left( {c,d} \right)S\left( {e,f} \right),\) then multiplying both equations, we can write

\[{\left\{ \begin{array}{l} ad = bc\\ cf = de \end{array} \right.,}\;\; \Rightarrow {adcf = bcde,}\;\; \Rightarrow {af\left( {cd} \right) = be\left( {cd} \right).}\]

If \(c \ne 0,\) then as \(d \ne 0,\) we have \(cd \ne 0,\) and \(af =be.\)

If \(c = 0,\) then it follows from the first equation that \(ad = 0.\) Since \(d \ne 0,\) then \(a = 0\) and, hence, \(af = 0.\) From the other side, if \(c = 0,\) then \(cf =0\) and \(de = 0\) as it follows from the second equation. This means that \(e = 0\) since \(d \ne 0.\) Consequently, \(be = 0,\) so we again conclude that \(af = be\) or \(\left( {a,b} \right)S\left( {e,f} \right).\)

We see that \(S\) is reflexive, symmetric, and transitive. Thus the relation \(S\) is an equivalence relation.

### Example 7.

A binary relation \(R\) is given by the matrix \[{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&0&0&0\\ 0&0&0&1\\ 0&0&0&1 \end{array}} \right].\] Determine the equivalence relation closure of \(R.\)Solution.

We calculate the equivalence relation closure \(tsr\left( R \right)\) in matrix form by the formula

\[tsr\left( R \right) = {\left( {R \cup I \cup {R^{ – 1}}} \right)^*},\]

where \(I\) is the identity relation, \(R^{-1}\) is the inverse relation, and the asterisk symbol \(^{*}\) denotes the connectivity relation.

First we find the reflexive closure \(r\left( R \right):\)

\[{{M_{r\left( R \right)}} = {M_R} + {M_I} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&0&0&0\\ 0&0&0&1\\ 0&0&0&1 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&0&0\\ 0&\color{red}{1}&0&0\\ 0&0&\color{red}{1}&0\\ 0&0&0&\color{red}{1} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ 0&0&\color{red}{1}&1\\ 0&0&0&1 \end{array}} \right].}\]

Next, we calculate the symmetric closure \(s\left( {r\left( R \right)} \right).\) The matrix of the inverse relation \(R^{-1}\) has the form

\[{M_{{R^{ – 1}}}} = \left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&0&0&0\\ \color{red}{1}&0&0&0\\ 0&0&\color{red}{1}&1 \end{array}} \right].\]

Then

\[{{M_{s\left( {r\left( R \right)} \right)}} = {M_R} + {M_I} + {M_{{R^{ – 1}}}} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ 0&0&\color{red}{1}&1\\ 0&0&0&1 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 0&0&0&0\\ \color{red}{1}&0&0&0\\ 0&0&\color{red}{1}&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right].}\]

We denote the symmetric closure \(s\left( {r\left( R \right)} \right)\) by \(S\) for brevity, so

\[{M_S} = \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right].\]

Now we can compute the connectivity relation \(S^{*},\) which coincides with the equivalence relation closure \(tsr\left( R \right).\) The connectivity relation is given by the formula

\[{{S^*} = tsr\left( R \right) }={ S \cup {S^2} \cup {S^3} \cup {S^4}.}\]

Determine the compositions of relations \({S^2},{S^3}, \ldots \) using matrix multiplication:

\[{{M_{{S^2}}} = {M_S} \times {M_S} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&\color{red}{1}\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ \color{red}{1}&0&\color{red}{1}&1 \end{array}} \right].}\]

\[{{M_{{S^3}}} = {M_{{S^2}}} \times {M_S} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&\color{red}{1}\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ \color{red}{1}&0&\color{red}{1}&1 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&\color{red}{1}\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ \color{red}{1}&0&\color{red}{1}&1 \end{array}} \right].}\]

As it can be seen, \({M_{{S^3}}} = {M_{{S^2}}}.\) So we can determine the connectivity relation \(S^{*}\) by the simplified formula

\[{S^*} = tsr\left( R \right) = S \cup {S^2}.\]

Thus, the matrix of the equivalence relation closure \(tsr\left( R \right)\) is given by

\[{{M_{tsr\left( R \right)}} = {M_{{S^*}}} }={ {M_S} + {M_{{S^2}}} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&0\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ 0&0&\color{red}{1}&1 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} 1&0&1&\color{red}{1}\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ \color{red}{1}&0&\color{red}{1}&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1&\color{red}{1}\\ 0&\color{red}{1}&0&0\\ \color{red}{1}&0&\color{red}{1}&1\\ \color{red}{1}&0&\color{red}{1}&1 \end{array}} \right].}\]

The solution can also be represented by the digraph: