Transitive Closure Always Exists (Relation Theory)/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then the transitive closure $\RR^+$ of $\RR$ always exists.


Proof

First, note that there exists at least one transitive relation containing $\RR$.

That is, the trivial relation $S \times S$, which is an equivalence and therefore transitive by definition.

Next, note that the Intersection of Transitive Relations is Transitive.

Hence the transitive closure of $\RR$ is the intersection of all transitive relations containing $\RR$.


Also see