0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I changed the answer as well. $\endgroup$ – Danuso Rocha Mar 26 '17 at 9:11
1
$\begingroup$

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

Edit:

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – UserAb Mar 26 '17 at 13:16
  • $\begingroup$ Sorry. I forgot the "not". I am going to correct that. $\endgroup$ – Danuso Rocha Mar 26 '17 at 14:36

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.