equivalence relation composition problem

Question

Let $R_1$, $R_2$ be two equivalence relations on $X$, prove that $R_1\circ R_2$ is an equivalence relation if and only if $R_1\circ R_2= R_2\circ R_1$

First I´m trying to prove that $R_1\circ R_2= R_2\circ R_1$ $\Rightarrow R_1\circ R_2$ is an equivalence relation; I have already shown that $R_1\circ R_2$ is reflexive and symmetric; to prove that is transitive: $(x,y)\in R_1\circ R_2$ and $(y,z)\in R_1\circ R_2$ $\Rightarrow (x,z)\in R_1\circ R_2$ but I don´t how to proceed from here, I would appreciate your help

Answer 1

I'm going to give this a shot (but to be honest I haven't worked with "composition" of relations before so I'm hoping I found the correct definition).

From my understanding, $R_1\circ R_2$ is interpreted as: $(x,y) \in R_1\circ R_2$ if there exists some other element $\alpha\in X$ such that $(x,\alpha)\in R_1 $ and $(\alpha,y)\in R_2$.

So here's my proof:

Using the definition above,

$(x,y)\in R_1\circ R_2$ means there is some $t\in X$ such that $(x,t)\in R_1$ and $(t,y)\in R_2$.

$(y,z)\in R_1\circ R_2$ means there is some $s\in X$ such that $(y,s)\in R_1$ and $(s,z)\in R_2$.

Then from the assumption we have that $R_1\circ R_2= R_2\circ R_1$. So we can also say:

$(x,y)\in R_1\circ R_2 = R_2\circ R_1\Rightarrow (x,t)\in R_2 \text{ and } (t,y)\in R_1$.

$(y,z)\in R_1\circ R_2 = R_2\circ R_1\Rightarrow (y,s)\in R_2 \text{ and } (s,z)\in R_1$.

So taking all the bits we need: $$(x,t)\in R_1, (t,y)\in R_1 \Rightarrow (x,y)\in R_1$$ $$(y,s)\in R_2, (s,z)\in R_2 \Rightarrow (y,z)\in R_2$$ (and these follow because $R_1$ and $R_2$ are each transitive equivalence relations).

Then put these together and you get $$(x,y)\in R_1\text{ and }(y,z)\in R_2 \Rightarrow (x,z)\in R_1\circ R_2$$

Which shows that if $(x,y)\in R_1\circ R_2$ and $(y,z)\in R_1\circ R_2$ then $(x,z)\in R_1\circ R_2$.

Answer 2

Let $x,y,z\in A$. Suppose $(x,y)\in R_1 \circ R_2 \wedge (y,z)\in R_1 \circ R_2$

Because $(x,y)\in R_1\circ R_2$ then there is a $t\in A$ such that $(x,t)\in R_1$ and $(t,y)\in R_2$.

Because $(y,z)\in R_1\circ R_2$ then there is a $s\in A$ such that $(y,s)\in R_1$ and $(s,z)\in R_2$.

Also because $R_1$, $R_2$ are symmetric, $(s,y)\in R_1$ and $(y,t)\in R_2$, wich means that $(s,t)\in R_1\circ R_2 $.

Now suppose that $R_1\circ R_2= R_2\circ R_1$ then we can say that:

$(s,t)\in R_2\circ R_1 $ and the therefore there is a $k\in A$ such that $(s,k)\in R_2$ and $(k,t)\in R_1$.

Using again that $R_1$ and $R_2$ are symmetric we have that $(k,s)\in R_2$ and $(t,k)\in R_1$

Joining some of this results and considering that $R_1$, $R_2$ are transitive we have

1. $(x,t)\in R_1 \wedge (t,k)\in R_1 \Rightarrow (x,k)\in R_1$

2. $(k,s)\in R_2 \wedge (s,z)\in R_2 \Rightarrow (k,z)\in R_2$

$$ \Rightarrow (x,z)\in R_1\circ R_2$$

We have proven that if $R_1\circ R_2= R_2\circ R_1$ $$(x,y)\in R_1\circ R_2\text{ and }(y,z)\in R_1\circ R_2 \Rightarrow (x,z)\in R_1\circ R_2$$

In other words, that $R_1\circ R_2$ is transitive

$\blacksquare$