Equivalence iff Diagonal and Inverse Composite

Theorem

Let $\mathcal R$ be a relation on $S$.

Then $\mathcal R$ is an equivalence relation on $S$ iff $\Delta_S \subseteq \mathcal R$ and $\mathcal R = \mathcal R \circ \mathcal R^{-1}$.

Proof

Necessary Condition

Let $\mathcal R$ be an equivalence relation.

Then by definition, it is reflexive, symmetric and transitive.

As $\mathcal R$ is reflexive, we have $\Delta_S \subseteq \mathcal R$ from Reflexive contains Diagonal Relation.

As $\mathcal R$ is transitive, we have $\mathcal R \circ \mathcal R \subseteq \mathcal R$ from Transitive Relation contains Composite with Self.

But as $\mathcal R$ is symmetric, we also have $\mathcal R = \mathcal R^{-1}$ from Relation equals Inverse iff Symmetric.

Thus $\mathcal R \circ \mathcal R^{-1} \subseteq \mathcal R$.

Now we need to show that $\mathcal R \subseteq \mathcal R \circ \mathcal R^{-1}$:

Let $\left({x, y}\right) \in \mathcal R$.

Then as $\mathcal R$ is reflexive, $\left({x, y}\right) \in \mathcal R \land \left({y, y}\right) \in \mathcal R$ and so $\left({x, y}\right) \in \mathcal R \circ \mathcal R$.

As $\mathcal R = \mathcal R^{-1}$, it follows that $\mathcal R \subseteq \mathcal R \circ \mathcal R^{-1}$.

So the first part has been shown: $\Delta_S \subseteq \mathcal R$ and $\mathcal R = \mathcal R \circ \mathcal R^{-1}$.

$\Box$

Sufficient Condition

Now, let $\Delta_S \subseteq \mathcal R$ and $\mathcal R = \mathcal R \circ \mathcal R^{-1}$.

From Reflexive contains Diagonal Relation, $\mathcal R$ is reflexive.

Suppose $\left({x, y}\right) \in \mathcal R$.

Then $\left({x, y}\right) \in \mathcal R \circ \mathcal R^{-1}$.

So $\exists z \in S: \left({x, z}\right) \in \mathcal R, \left({z, y}\right) \in \mathcal R^{-1}$, and so $\left({y, z}\right) \in \mathcal R$.

Thus it follows that $\mathcal R$ is transitive.

And as $\left({x, z}\right) \in \mathcal R$, it follows that $\left({z, x}\right) \in \mathcal R^{-1}$ and so it follows that $\left({y, x}\right) \in \mathcal R$.

So it follows that $\mathcal R$ is symmetric.

Thus $\mathcal R$ is reflexive, symmetric and transitive and therefore an equivalence relation.

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965): $\S 10$: Exercises $10.7$