Transitive Closure Always Exists (Relation Theory)/Outline

Theorem

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

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

Outline of 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$.