Simple exercise taken from the book Types and Programming Languages by Benjamin C. Pierce.
This is a definition of the transitive closure of a relation R.
First, we define the sequence of sets of pairs:
$$R_0 = R$$
$$R_{i+1} = R_i \cup \{ (s, u) | \exists t, (s, t) \in R_i, (t, u) \in R_i \}$$
Finally, define the relation $R^+$ as the union of all the $R_i$:
$$R^+=\bigcup_i R_i$$
Show that $R^+$ is really the transitive closure of R.
Questions:
- I would like to see the proof (I don't have enough mathematical background to make it myself).
- Isn't the final union superfluous? Won't $R_n$ be the union of all previous sequences?
Best Answer
First of all, if this is how you define the transitive closure, then the proof is over. But you may still want to see that it is a transitive relation, and that it is contained in any other transitive relation extending $R$.
To the second question, the answer is simple, no the last union is not superfluous because it is infinite. Every step contains a bit more, but not necessarily all the needed information.
So let us see that $R^+$ is really transitive, contains $R$ and is contained in any other transitive relation extending $R$.