Connected Equivalence Relation is Trivial

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R$ be a relation on $S$ which is both connected and an equivalence relation.


Then $\mathcal R$ is the trivial relation on $S$.


Proof

By definition of equivalence relation, $\mathcal R$ is an equivalence relation if and only if:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$


From Relation is Connected iff Union with Inverse and Diagonal is Trivial Relation:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R = S \times S$

Hence the result.

$\blacksquare$


Examples

Arbitrary Set of 4 Elements

Let $V = \set {a, b, c, d}$.

Let $S \subseteq V \times V$ such that:

$S = \set {\tuple {a, b}, \tuple {b, c}, \tuple {c, d} }$

Let $\mathcal R$ be an equivalence relation on $V$ such that:

$S \subseteq \mathcal R$

Then $\mathcal R$ is the trivial relation on $S$.