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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R$ be a relation on a set $S$.


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


Proof

Note that the trivial relation $\mathcal T = S \times S$ on $S$ contains $\mathcal R$, by the definition of a relation on $S$.

Further, $\mathcal T$ is transitive by Trivial Relation is Equivalence.


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

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

$\displaystyle \mathcal R^+ := \bigcap \left\{{\mathcal R': \text{$\mathcal R'$ is transitive and $\mathcal R \subseteq \mathcal R'$}}\right\}$


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

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

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


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

$\blacksquare$