Construction of Transitive Closure of Relation

From ProofWiki
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.




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


Sources