Find a Transitive closure on the relation R

Question

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$

Answer 1

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)\}$.

Answer 2

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$$