3
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ How do you define the transitive closure? $\endgroup$ – Asaf Karagila Apr 5 '13 at 9:50
  • $\begingroup$ @AsafKaragila According to the book: Transitive closure of R is the smalles transitive relation R' that contains R. $\endgroup$ – Maxym Apr 5 '13 at 9:55
  • 1
    $\begingroup$ @Maxym: A proof is available at ProofWiki. $\endgroup$ – Lord_Farin Apr 5 '13 at 9:57
  • 1
    $\begingroup$ @Maxym, its true that for all $n \in \mathbb{N}$ it holds that $R_n = \bigcup_{i=0}^n R_i$. But the final union is not superfluous, because $R^+$ is essentially the same as $R_\infty$, and we never get to infinity. $\endgroup$ – goblin GONE Apr 5 '13 at 10:04
  • 2
    $\begingroup$ @Maxym: I answered the second question in my answer. $\endgroup$ – Asaf Karagila Apr 5 '13 at 10:04
8
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ About the second question - so in the other words - we just don't know what is n, And if we have infinite union that we don't need to know what is n, right? $\endgroup$ – Maxym Apr 5 '13 at 10:08
  • 3
    $\begingroup$ @Maxym: To show that the infinite union is necessary, you can consider $\mathcal R$ defined on $\Bbb N$ by putting $m \mathrel{\mathcal R} n$ iff $n = m+1$. $\endgroup$ – Lord_Farin Apr 5 '13 at 10:12
4
$\begingroup$

We need to show that $R^+$ contains $R$, is transitive, and is minmal among all such relations.

$R\subseteq R^+$ is clear from $R=R_0\subseteq \bigcup R_i=R^+$.

Transitivity: By induction on $j$, show that $R_i\subseteq R_j$ if $i\le j$. Assume $(a,b), (b,c)\in R^+$. Then $(a,b)\in R_i$ for some $i$ and $(b,c)\in R_j$ for some $j$. This implies $(a,b),(b,c)\in R_{\max(i,j)}$ and hence $(a,c)\in R_{\max(i,j)+1}\subseteq R^+$.

Now for minimality, let $R'$ be transitive and containing $R$. By induction show that $R_i\subseteq R'$ for all $i$, hence $R^+\subseteq R'$, as was to be shown.

As for your specific question #2: Yes, $R_n$ contains all previous $R_k$ (a fact, the proof above uses as intermediate result). But neither is $R_n$ merely the union of all previous $R_k$, nor does there necessarily exist a single $n$ that already equals $R^+$. For example, on $\mathbb N$ take the realtaion $aRb\iff a=b+1$. Then $aR^+b\iff a>b$, but $aR_nb$ implies that additionally $a\le b+2^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.