Transitive Closure of Reflexive Relation is Reflexive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\RR$ be a reflexive relation on $S$.

Let $\RR^+$ be the transitive closure of $\RR$.


Then $\RR^+$ is reflexive.


Proof

Let $a \in S$.

Since $\RR$ is reflexive:

$\tuple {a, a} \in \RR$

By the definition of transitive closure:

$\RR \subseteq \RR^+$

Thus by the definition of subset:

$\tuple {a, a} \in \RR^+$

Since this holds for all $a \in S$, it follows that $\RR^+$ is reflexive.

$\blacksquare$


Also see