Transitivity of $R$ when it is a relation such that $R^2 = R$ and Vice-Versa.

1.1k Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.