0
$\begingroup$

My question is about Set and Relation Theory.

$R$ is a relation on a set $S$.

1) Show that if $R^2 = R$ then $R$ is transitive.

2) Show that if $R$ is transitive and "Reflexive or Symmetric" Then $R=R^2$. (It means that for a transitive and reflexive relation we have $R = R^2$ and for a transitive and Symmetric relation we have $R=R^2$)

For 1, My proof is: Let $aRb$ and $bRc$ then by definition of R^2 we have $a R^2 b$ and because $R^2 = R$, we have $a R c$. so $R$ is transitive.

But I don't know what to do for 2.

Is my answer to "1)" correct? How to approach 2?

$\endgroup$
5
  • $\begingroup$ Can you prove that if $R$ is transitive, then $R^2\subseteq R$? What are you missing to be able to prove the other inclusion? How would “reflexive” help? How would “symmetric” help? $\endgroup$ – Arturo Magidin Jun 1 '19 at 18:33
  • $\begingroup$ @ArturoMagidin yes. I can prove that. but we will also need to show that $R \subseteq R^2$. Can i get this from "reflexive" or "symmetric"? $\endgroup$ – amir na Jun 1 '19 at 18:35
  • $\begingroup$ @ArturoMagidin Actually I need to prove that if $aRb$ then there exist a c such that $aRc$ and $cRb$? So I think when it is reflexive that c is $a$ yes? $\endgroup$ – amir na Jun 1 '19 at 18:37
  • $\begingroup$ @ArturoMagidin also, If we exclude the empty elements that are isolated, we can say that for the rest, if relation is symmetric and transitive, it is also reflexive. yes? $\endgroup$ – amir na Jun 1 '19 at 18:41
  • $\begingroup$ That was my question: how can you use “reflexive” to get $R\subseteq R^2$? Yes, you need to show that if $aRb$, then there exists $c$ such that $aRc$ and $cRb$. Would “reflexive” help you there? How about “symmetric”? $\endgroup$ – Arturo Magidin Jun 1 '19 at 18:51
2
$\begingroup$

Your answer to the first question is correct.

Now, suppose that $R$ is transitive and reflexive. You want to prove that $R=R^2$. If $a\mathrel Rb$, then, since $b\mathrel Rb$ and $R$ is transitive, $a\mathrel{R^2}b$. So, $R\subset R^2$. And if $a\mathrel{R^2}b$, then there is a $c$ such that $a\mathrel Rc$ and $c\mathrel b$. So, since $R$ is transitive, $a\mathrel Rb$. This proves that $R^2\subset R$. So, $R^2=R$.

Finally, suppose that $R$ is transitive and symmetric. Again, you want to prove that $R=R^2$. If $a\mathrel Rb$, then, since $R$ is symmetric, $b\mathrel Ra$. And, since $b\mathrel Ra$, $a\mathrel Rb$ and $R$ is transitive, $b\mathrel Rb$. Now, since $a\mathrel Rb$, and $b\mathrel Rb$, $a\mathrel{R^2}b$. So, $R\subset R^2$ and you can prove that $R^2\subset R$ as above.

$\endgroup$
1
  • $\begingroup$ I am now sure that my answer to the second question in comments is also right. Thank you very much. $\endgroup$ – amir na Jun 1 '19 at 18:43

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.