Transitive Closure Always Exists (Relation Theory)
Theorem
Let $\RR$ be a relation on a set $S$.
Then the transitive closure $\RR^+$ of $\RR$ always exists.
Proof
Outline
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$.
$\Box$
By definition, the trivial relation $\TT = S \times S$ on $S$ contains $\RR$ as a subset.
Further, $\TT$ is transitive by Trivial Relation is Equivalence.
Thus there exists at least one transitive relation on $S$ that contains $\RR$.
Let $\RR^\cap$ be defined as the intersection of all transitive relations on $S$ that contain $\RR$:
- $\ds \RR^\cap := \bigcap \set {\RR': \RR' \text{ is transitive and } \RR \subseteq \RR'}$
By Intersection of Transitive Relations is Transitive, $\RR^\cap$ is also a transitive relation on $S$.
By Set Intersection Preserves Subsets, it also holds that $\RR \subseteq \RR^\cap$.
Lastly, by Intersection is Subset, for any transitive relation $\RR'$ containing $\RR$, it must be that $\RR^\cap \subseteq \RR'$.
Thus $\RR^\cap$ is indeed the minimal transitive relation on $S$ containing $\RR$.
That is, $\RR^+ = \RR^\cap$, and thence the transitive closure of $\RR$ exists.
$\blacksquare$