Connected Equivalence Relation is Trivial
Jump to navigation
Jump to search
Theorem
Let $S$ be a set.
Let $\RR$ be a relation on $S$ which is both connected and an equivalence relation.
Then $\RR$ is the trivial relation on $S$.
Proof
By definition of equivalence relation, $\RR$ is an equivalence relation if and only if:
- $\Delta_S \cup \RR^{-1} \cup \RR \circ \RR \subseteq \RR$
From Relation is Connected iff Union with Inverse and Diagonal is Trivial Relation:
- $\Delta_S \cup \RR^{-1} \cup \RR = 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 $\RR$ be an equivalence relation on $V$ such that:
- $S \subseteq \RR$
Then $\RR$ is the trivial relation on $S$.