Equivalence of Definitions of Transitive Closure (Relation Theory)/Intersection is Smallest

Theorem

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

Then the intersection of all transitive relations on $S$ that contain $\RR$ is the smallest transitive relation on $S$ that contains $\RR$.

Proof

Note that the trivial relation $\TT = S \times S$ on $S$ contains $\RR$, by the definition of a relation on $S$.

Further, $\TT$ is transitive by Trivial Relation is Equivalence.

Thus there is at least one transitive relation on $S$ that contains $\RR$.

Now define $\RR^+$ as the intersection of all transitive relations on $S$ that contain $\RR$:

$\ds \RR^+ := \bigcap \set {\RR': \text {$\RR'$ is transitive and $\RR \subseteq \RR'$} }$

By Intersection of Transitive Relations is Transitive, $\RR^+$ is also a transitive relation on $S$.

By Set Intersection Preserves Subsets, it also holds that $\RR \subseteq \RR^+$.

Lastly, by Intersection is Subset, for any transitive relation $\RR'$ containing $\RR$, it must be that $\RR^+ \subseteq \RR'$.

Thus $\RR^+$ is indeed the smallest transitive relation on $S$ containing $\RR$.

$\blacksquare$