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?