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

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 1

First, note that there exists at least one transitive relation containing $\mathcal R$.

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 $\mathcal R$ is the intersection of all transitive relations containing $\mathcal R$.


Proof 2

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

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^\cap$ as the intersection of all transitive relations on $S$ that contain $\mathcal R$:

$\displaystyle \mathcal R^\cap := \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^\cap$ is also a transitive relation on $S$.

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

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


Thus $\mathcal R^\cap$ is indeed the minimal transitive relation on $S$ containing $\mathcal R$.

That is, $\mathcal R^+ = \mathcal R^\cap$, and thence the transitive closure of $\mathcal R$ exists.

$\blacksquare$