# Transitive closure of relation

Let $R$ be a binary relation on set X. Let us define the transitive closure of $R$, denoted by $S_R$ as follows:
$xS_Ry$, if $xRy$ or there exist $x_1,x_2,…, x_m\in X$ such that $xRx_1,x_1Rx_2, …, x_{m–1}Rx_m, x_mRy$.

Then how can we prove that

1. $S_R$ is transitive
2. $S_R$ is asymmetric if and only if it is irreflexive.

Thanks.

• I changed the answer as well. Mar 26, 2017 at 9:11

If $xS_Ry$ and $yS_Rz$, so there are $\{x_1,..., x_m\}$ and $\{ y_1,...,y_n \}$ such that $xRx_1, x_1Rx_2,..., x_{m-1}Rx_m, x_mRy$ and $yRy_1, y_1Ry_2,..., y_{n-1}Ry_n, y_nRz$. Denote $x_{m+1}:= y$ and $x_{m+i+1}:=y_i$. Therefore, $xRx_1, x_1Rx_2,..., x_{m-1}Rx_m, x_mRx_{m+1}, ..., x_{m+n+1}Rz$. Hence, $xS_Rz$.
To solve 2, it's easy to see that asymmetric implies ireflexive. Because if you suppose that $S_R$ is not ireflexive, so there is $aS_Ra$. Therefore, choose $b=a$ and we have $aS_Rb$ and $bS_Ra$. So $S_R$ would not be asymmetric.
Now we are going to prove that if $S_R$ is not asymmetric implies $S_R$ is not ireflexive. If $S_R$ is not asymmetric, there are $a_0$ and $b_0$ such that $a_0S_Rb_0$ and $b_0S_Ra_0$. Therefore, for transitiveness, $a_0 S_R a_0$. Hence $S_R$ is not ireflexive.
• Thanks, but I don't understand the second proof. I.e. If $S_R$ is asymmetric, there are $a_0$ and $b_0$ such that $a_0S_Rb_0$ and $b_0S_Ra_0$? Here it seems symmetric. Do you mean if $S_R$ is $\textbf{not}$ $\textbf{asymmetric}$ instead? Mar 26, 2017 at 13:16