As part of a HW assignment in the course elementary set theory, I was given the following question:
Let $A$ be a set and let $T$ and $S$ be two equivalence relations on $A$.
Prove: $S\circ T=T\circ S \iff S\circ T$ is an equivalence relation
The $\Longleftarrow $ direction was not so difficult but I had a problem with the $\Longrightarrow $ direction.
I managed to prove reflexiveness and symmetry of $S\circ T$, but cannot prove the transitivity of $S\circ T$.
Any suggestions?
A relation $R$ is transitive iff $R \circ R \subseteq R$.
So we need to prove $(S\circ T)\circ(S\circ T) \subseteq S \circ T$. Note that the brackets are optional -- composition of relations is associative.
Can you see how the assumption $S \circ T = T \circ S$ helps us here? (Remember that $S$ and $T$ are also equivalence relations.)