Recursive Construction of Transitive Closure

From ProofWiki
Jump to navigation Jump to search

Theorem

Given the relation $\mathcal R$, its transitive closure $\mathcal R^+$ can be constructed as follows:

Let:

$\mathcal R_n := \begin{cases} \mathcal R & : n = 0 \\ \mathcal R_{n-1} \cup \left\{{\left({x_1, x_3}\right): \exists x_2: \left({x_1, x_2}\right) \in \mathcal R_{n-1} \land \left({x_2, x_3}\right) \in \mathcal R_{n-1}}\right\} & : n > 0 \end{cases}$

Finally, let:

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

Then $R^+$ is the transitive closure of $R$.


Proof

We must show that:

  • $\mathcal R \subseteq \mathcal R^+$
  • $\mathcal R^+$ is transitive
  • $\mathcal R^+$ is the smallest relation with both of those characteristics.


Proof of Subset

$\mathcal R \subseteq \mathcal R^+$: $\mathcal R^+$ contains all of the $\mathcal R_i$, so in particular $\mathcal R^+$ contains $\mathcal R$.


Proof of Transitivity

Every element of $\mathcal R^+$ is in one of the $\mathcal R_i$.

From the method of construction of $\mathcal R^+$, we have that $\forall i, j \in \N: \mathcal R_i \subseteq \mathcal R_{\max \left({i, j}\right)}$.

Suppose $\left({s_1, s_2}\right) \in \mathcal R_j$ and $\left({s_2, s_3}\right) \in \mathcal R_k$.

Then as:

$\mathcal R_j \subseteq \mathcal R_{\max \left({j, k}\right)}$

and:

$\mathcal R_k \subseteq \mathcal R_{\max \left({j, k}\right)}$

it follows that:

$\left({s_1, s_2}\right) \in \mathcal R_{\max \left({j, k}\right)}$ and $\left({s_2, s_3}\right) \in \mathcal R_{\max \left({j, k}\right)}$

It follows from the method of construction that $\left({s_1, s_3}\right) \in \mathcal R_{\max \left({j, k}\right)}$.


Hence as $\mathcal R_{\max \left({j, k}\right)} \subseteq \mathcal R^+$, it follows that $\mathcal R^+$ is transitive.


Proof of being the smallest such relation

Let $\mathcal R'$ be any transitive relation containing $\mathcal R$.

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

It is sufficient to show that $\forall i \in \N: \mathcal R_i \subseteq \mathcal R'$.


Since $\mathcal R \subseteq \mathcal R'$, we have that $\mathcal R_0 \subseteq \mathcal R'$.

Suppose $\mathcal R_i \subseteq \mathcal R'$.

From the method of construction, as $\mathcal R'$ is transitive, $\mathcal R_{i+1} \subseteq \mathcal R'$.

Therefore, by induction, $\forall i \in \N: \mathcal R_i \subseteq \mathcal R'$.

So $\mathcal R^+ \subseteq \mathcal R'$, and hence the result.

$\blacksquare$