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

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let:

$\mathcal R^n := \begin{cases} \mathcal R & : n = 0 \\ \mathcal R^{n-1} \circ \mathcal R & : n > 0 \end{cases}$

where $\circ$ denotes composition of relations.



Finally, let:

$\displaystyle \mathcal R^+ = \bigcup_{i \mathop \in \N} \mathcal R^i$


Then $\mathcal R^+$ is the smallest transitive relation on $S$ that contains $\mathcal R$.


Proof

$\mathcal R^+$ is Transitive

By Relation contains Composite with Self iff Transitive, we can prove that $\mathcal R^+$ is transitive by proving the following:

$\mathcal R^+ \circ \mathcal R^+ \subseteq \mathcal R^+$


Let $\left({a, c}\right) \in \mathcal R^+ \circ \mathcal R^+$.

Then:

$\exists b \in S: \left({a, b}\right) \in \mathcal R^+, \left({b, c}\right) \in \mathcal R^+$

Thus:

$\exists n \in \N: \left({a, b}\right) \in \mathcal R^n$
$\exists m \in \N: \left({b, c}\right) \in \mathcal R^m$

From Composition of Relations is Associative:

$R^{n + m} = R^n \circ R^m$

so:

$\left({a, c}\right) \in \mathcal R^{n + m} \subseteq \mathcal R^+$

Since this holds for all $\left({a, c}\right) \in \mathcal R^+ \circ \mathcal R^+$:

$\mathcal R^+ \circ \mathcal R^+ \subseteq \mathcal R^+$

Thus $\mathcal R^+$ is transitive.

$\Box$


$\mathcal R^+$ contains $\mathcal R$

$\mathcal R \subseteq \mathcal R^+$ by Set is Subset of Union.


$\mathcal R^+$ is Smallest

Let $\mathcal R'$ be a transitive relation on $S$ such that $\mathcal R \subseteq \mathcal R'$.

We must show that $\mathcal R^+ \subseteq \mathcal R'$.

Let $\left({a, b}\right) \in \mathcal R^+$.

That is:

$a \mathrel{\mathcal R} b$

Then:

$\exists n \in \N: \left({a, b}\right) \in \mathcal R^n$

Thus by the definition of composition of relations, there exists $x_{n-1} \in S$ such that:

$a \mathrel {\mathcal R^{n-1}} x_{n-1} \wedge x_{n-1} \mathrel {\mathcal R} b$

Likewise there exists $x_{n-2} \in S$ such that:

$a \mathrel {\mathcal R^{n-2}} x_{n-2} \wedge x_{n-2} \mathrel {R} x_{n-1}$

And so forth there exist elements $x_0, \dots, x_n \in S$ such that:

$x_0 = a$
$x_n = b$
$\forall k \in \N_n: x_k \mathrel {\mathcal R} x_{k + 1}$

Since $\mathcal R \subseteq \mathcal R'$:

$\forall k \in \N_n: x_k \mathrel {\mathcal R'} x_{k + 1}$

Since $\mathcal R'$ is transitive:

$a \mathrel{\mathcal R'} b$

That is:

$\left({a, b}\right) \in \mathcal R'$

Since this holds for all $\left({a, b}\right) \in \mathcal R^+$:

$\mathcal R^+ \subseteq \mathcal R'$

Since this holds for all transitive relations $\mathcal R'$ that contain $\mathcal R$:

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

$\blacksquare$