Transitive Closure of Reflexive Relation is Reflexive
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$