Transitive Closure of Reflexive Symmetric Relation is Equivalence

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a set.

Let $\mathcal R$ be a symmetric and reflexive relation on $S$.

Then the transitive closure of $\mathcal R$ is an equivalence relation.


Let $\sim$ be the transitive closure of $\mathcal R$.

Checking in turn each of the criteria for equivalence:


By Transitive Closure of Reflexive Relation is Reflexive:

$\sim$ is reflexive.



By Transitive Closure of Symmetric Relation is Symmetric:

$\sim$ is symmetric.



By the definition of transitive closure:

$\sim$ is transitive.


$\sim$ has been shown to be reflexive, symmetric and transitive.

Hence by definition it is an equivalence relation.