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

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

Let $\mathcal R^+$ be the intersection of all transitive relations containing $\mathcal R$

By Trivial Relation is Equivalence: the trivial relation $S \times S$ is transitive.

Note also that by the definition of endorelation, $\mathcal R \subseteq S \times S$.

Next, note that the Intersection of Transitive Relations is Transitive.


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