Equivalence Relations

Solved Problems

Solution.

1. $$ is an equivalence relation since it is reflexive, symmetric, and transitive.
2. $$ is not reflexive since $$ $$ is not symmetric because $$ but $$ $$ is not transitive: $$ but $$ Hence, $$ is not an equivalence relation.
3. $$ is an equivalence relation since it is reflexive, symmetric, and transitive.
4. $$ is not symmetric since $$ but $$ Similarly $$ but $$ Thus $$ is not an equivalence relation.

Solution.

1. Obviously, $$ speaks the same language, so this relation is reflexive. If $$ speaks the same language as $$ then $$ speaks the same language as $$ so this relation is symmetric. If $$ speaks the same language as $$ and $$ speaks the same language as $$ then $$ speaks the same language as $$ 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, $$ and $$ speak a common language, say French, and $$ and $$ speak another common language, say German. This means that $$ and $$ 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 $$ $$ and $$ are located on the same straight line. If the distance between $$ and $$ is $$ miles, and the distance between $$ and $$ is also $$ miles, the distance between $$ and $$ may be equal to $$ 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 $$ loves $$ then it may be that $$ loves $$ 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: $$ as not older than itself. This relation is not symmetric: If $$ is older than $$ than the converse is false. This relation is transitive: if $$ is older than $$ and $$ is older than $$ then $$ is older than $$ Given these properties, we conclude that this is not an equivalence relation.

Example 3.

Determine whether the relation $$ given by the digraph is an equivalence relation.

Solution.

The relation $$ is reflexive and transitive, but it is not symmetric: $$ but $$ Similarly two other edges $$ and $$ Hence, the relation $$ is not an equivalence relation. The missing edges are marked in red.

Example 4.

Determine whether the relation $$ given by the digraph is an equivalence relation.

Solution.

The relation $$ is not reflexive because the element $$ is missing. Thus, $$ is not an equivalence relation. We can build the equivalence closure of $$ by adding a self-loop to the node $$ on the digraph:

Solution.

Obviously, $$ is reflexive since $$

$$ is symmetric: if $$ and hence $$ then $$ is also an integer, so we have $$

$$ is transitive. Indeed, let $$ and $$ Then $$ and $$ where $$ are certain integers. By adding the two equations, we obtain

where $$ This proves the transitivity of $$

Thus, the relation $$ is an equivalence relation.

Solution.

The relation $$ is reflexive. Indeed, $$ is given by

The relation $$ is symmetric because $$ means that

Check $$ for the transitivity property. Since $$ and $$ then multiplying both equations, we can write

If $$ then as $$ we have $$ and $$

If $$ then it follows from the first equation that $$ Since $$ then $$ and, hence, $$ From the other side, if $$ then $$ and $$ as it follows from the second equation. This means that $$ since $$ Consequently, $$ so we again conclude that $$ or $$

We see that $$ is reflexive, symmetric, and transitive. Thus the relation $$ is an equivalence relation.

Solution.

We calculate the equivalence relation closure $$ in matrix form by the formula

where $$ is the identity relation, $$ is the inverse relation, and the asterisk symbol $$ denotes the connectivity relation.

First we find the reflexive closure $$

Next, we calculate the symmetric closure $$ The matrix of the inverse relation $$ has the form

Then

We denote the symmetric closure $$ by $$ for brevity, so

Now we can compute the connectivity relation $$ which coincides with the equivalence relation closure $$ The connectivity relation is given by the formula

Determine the compositions of relations $$ using matrix multiplication:

As it can be seen, $$ So we can determine the connectivity relation $$ by the simplified formula

Thus, the matrix of the equivalence relation closure $$ is given by

The solution can also be represented by the digraph: