Transitive Closure Always Exists (Relation Theory)

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 1

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


Proof 2

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$


Also see