Transitive Closure of Reflexive Symmetric Relation is Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

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.


Proof

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

Checking in turn each of the criteria for equivalence:


Reflexivity

By Transitive Closure of Reflexive Relation is Reflexive:

$\sim$ is reflexive.

$\Box$


Symmetry

By Transitive Closure of Symmetric Relation is Symmetric:

$\sim$ is symmetric.

$\Box$


Transitivity

By the definition of transitive closure:

$\sim$ is transitive.

$\Box$


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

Hence by definition it is an equivalence relation.

$\blacksquare$