[Math] Transitive closure proof (Pierce, ex. 2.2.7)

elementary-set-theoryrelations

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:

  1. I would like to see the proof (I don't have enough mathematical background to make it myself).
  2. 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$.

  1. Clearly $R\subseteq R^+$ because $R=R_0$.
  2. If $x,y,z$ are such that $x\mathrel{R^+} y$ and $y\mathrel{R^+}z$ then there is some $n$ such that $x\mathrel{R_n}y$ and $y\mathrel{R_n}z$, therefore in $R_{n+1}$ we add the pair $(x,z)$ and so $x\mathrel{R_{n+1}}z$ and therefore $x\mathrel{R^+}z$ as wanted.
  3. If $T$ is a transitive relation containing $R$, then one can show it contains $R_n$ for all $n$, and therefore their union $R^+$. To see that $R_n\subseteq T$ note that $R_0$ is such; and if $R_n\subseteq T$ and $(x,z)\in R_{n+1}$ then there is some $y$ such that $(x,y)\in R_n$ and $(y,z)\in R_n$. Since $R_n\subseteq T$ these pairs are in $T$, and since $T$ is transitive $(x,z)\in T$ as well.
Related Question