# Connected Equivalence Relation is Trivial

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$.