3

Find the transitive closure of $R=\{(a,b),(b,a),(b,c),(c,d),(c,e)\}$

I got the $R \circ R =\{(a,a),(a,c),(b,b),(b,d),(b,e)\}=R^2$

Graham Kemp
  • 129,094
  • 2
    You are asked to find the transitive closure of $R$ which is $\bigcup_{n=1}^{\infty}R^n$.So you made a start. Now carry on. As encouragement: the sequence of sets $(S_m)m$ with $S_m=\bigcup{n=1}^{m}R^n$ will stabilize quite soon. – drhab Jan 14 '18 at 13:41
  • Tip 1: The closure should include all the elements of the set being enclosed. So you need $R\cup R^2\cup...$ – Graham Kemp Jan 14 '18 at 13:41
  • But my method is rather tedious –  Jan 14 '18 at 13:45
  • 1
    You can also wonder: if I start in $a$ then is there a way to "reach" e.g. $c$ in steps $aRx_1, x_1Rx_2,\dots,x_kRc$?... If so then $(a,c)$ will belong to the closure. – drhab Jan 14 '18 at 13:48

2 Answers2

3

If I am right, transitive closure of $R$ is the smallest relation $\overline{R}\supset R$ that is transitive. To get to it, it is not enough to find $R\circ R=R^2$... you have to find $R\circ R\circ R=R^3$, then $R^4,R^5,\ldots$ and do it until $R\cup R^2\cup R^3\cup\cdots$ stabilises. The transitive closure is then that whole union.

In your case, I suspect you will finally end up with the relation $\overline{R}=\{(a,a),(a,b),(b,a),(b,b),(a,c),(b,c),(a,d),(b,d),(c,d),(a,e),(b,e),(c,e)\}$.

3

Hint:

An ordered pair $(p,q)$ will belong to the transitive closure of relation $R$ if and only if there is a finite sequence $x_0,x_1,\dots,x_n$ such that $p=x_0$, $q=x_n$ and:$$x_0Rx_1\wedge\cdots \wedge x_{n-1}Rx_n$$

drhab
  • 151,093