Calculus

Set Theory

Set Theory Logo

Equivalence Relations

Solved Problems

Example 1.

Which of these relations on the set \(A = \left\{ {1,2,3,4} \right\}\) are equivalence relations?

  1. \({R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.\) \(\left.{\left( {3,3} \right),\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.\)
  2. \({R_2} = \left\{ {\left( {1,4} \right),\left( {2,2} \right),\left( {3,3} \right),\left( {4,1} \right),} \right.\) \(\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.\)
  3. \({R_3} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,1} \right),} \right.\) \(\left.{\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),\left( {3,2} \right)} \right.\) \(\left.{\left( {3,3} \right),\left( {4,4} \right)} \right\}\)
  4. \({R_4} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,1} \right),\left( {4,4} \right)} \right\}.\)

Solution.

  1. \(R_1\) is an equivalence relation since it is reflexive, symmetric, and transitive.
  2. \(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.
  3. \(R_3\) is an equivalence relation since it is reflexive, symmetric, and transitive.
  4. \(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?

  1. \(a\) and \(b\) speak the same language.
  2. \(a\) and \(b\) speak a common language.
  3. \(a\) and \(b\) have the same mother.
  4. \(a\) lives within \(5\) miles of \(b.\)
  5. \(a\) loves \(b.\)
  6. \(a\) and \(b\) are younger than \(20.\)
  7. \(a\) is older than \(b.\)

Solution.

  1. 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.
  2. 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.
  3. This is an equivalence relation because it is reflexive, symmetric, and transitive.
  4. 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.
  5. 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.
  6. This relation is reflexive, symmetric, and transitive. Therefore, this is an equivalence relation.
  7. 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.

Example 1 - Is this binary relation 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.

Generating an equivalence relation R+.
Figure 1.

Example 4.

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

Example 2 - Is this binary relation 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:

Generating an equivalence relation S+.
Figure 2.

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

The equivalence relation closure of a binary relation R.
Figure 3.
Page 1 Page 2