Recursive Construction of Transitive Closure

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let:

$\RR_n := \begin{cases} \RR & : n = 0 \\ \RR_{n - 1} \cup \set {\tuple {x_1, x_3}: \exists x_2: \tuple {x_1, x_2} \in \RR_{n-1} \land \tuple {x_2, x_3} \in \RR_{n - 1} } & : n > 0 \end{cases}$

Finally, let:

$\ds \RR^+ = \bigcup_{i \mathop \in \N} \RR_i$.

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


Proof

We must show that:

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


Proof of Subset

$\RR \subseteq \RR^+$: $\RR^+$ contains all of the $\RR_i$, so in particular $\RR^+$ contains $\RR$.


Proof of Transitivity

Every element of $\RR^+$ is in one of the $\RR_i$.

From the method of construction of $\RR^+$:

$\forall i, j \in \N: \RR_i \subseteq \RR_{\max \set {i, j} }$

Suppose $\tuple {s_1, s_2} \in \RR_j$ and $\tuple {s_2, s_3} \in \RR_k$.

Then as:

$\RR_j \subseteq \RR_{\max \set {j, k} }$

and:

$\RR_k \subseteq \RR_{\max \set {j, k} }$

it follows that:

$\tuple {s_1, s_2} \in \RR_{\max \set {j, k} }$ and $\tuple {s_2, s_3} \in \RR_{\max \set {j, k} }$

It follows from the method of construction that:

$\tuple {s_1, s_3} \in \RR_{\max \set {j, k} }$


Hence as $\RR_{\max \set {j, k} } \subseteq \RR^+$, it follows that $\RR^+$ is transitive.


Proof of being the smallest such relation

Let $\RR'$ be any transitive relation containing $\RR$.

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

It is sufficient to show that $\forall i \in \N: \RR_i \subseteq \RR'$.


Since $\RR \subseteq \RR'$, we have that $\RR_0 \subseteq \RR'$.

Suppose $\RR_i \subseteq \RR'$.

From the method of construction, as $\RR'$ is transitive:

$\RR_{i + 1} \subseteq \RR'$

Therefore, by induction:

$\forall i \in \N: \RR_i \subseteq \RR'$

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

$\blacksquare$