# Construction of Transitive Closure of Relation

Jump to navigation
Jump to search

## Theorem

Let $\RR$ be a relation.

Let $\RR^+$ be the relation which is constructed from $\RR$ as follows:

- $(1): \quad$ If $\tuple {a, b} \in \RR$, then $\tuple {a, b} \in \RR^+$

- $(2): \quad$ If $\tuple {a, b} \in \RR^+$ and $\tuple {b, c} \in \RR$, then $\tuple {a, c} \in \RR^+$

- $(3): \quad$ Nothing is in $\RR^+$ unless it so follows from $(1)$ and $(2)$.

Then $\RR^+$ is the transitive closure of $\RR$.

## Proof

Let $\tuple {x, y} \in \R^+$ from rules $(1)$ and $(2)$.

Then either:

- $\tuple {x, y}$ belongs there because $\RR \subseteq \RR^+$

or:

- $\tuple {x, y}$ belongs there, because if it were not then $\RR^+$ would not be transitive.

It remains to be shown that $\RR^+$ is in fact transitive.

This needs considerable tedious hard slog to complete it.In particular: "Easy inductive proof", says H&U, that $\RR^+$ is in fact transitiveTo discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Finish}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

Because of the method of construction, it follows that $\RR^+$ is the smallest transitive relation on $S$ which contains $\RR$ as a subset.

## Sources

- 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.5$ Relations: Closures of Relations