For two binary relations R, S on a set X, we define their composition:
$\displaystyle R\circ S=\left\{(x,y)\in X\,|\,(\exists c\in X)\,xRc\,\wedge\,cSy\}\right$
I have proven two statements on this and am not sure about the third one. They're related so I'll post them all.
1. If R and S are commuting transitive relations on X, then their composition is also transitive.
Proof. Let $\displaystyle a\,R\circ S\,b$ and $\displaystyle b\,R\circ S\,c$ for some $\displaystyle a,b,c\in X.$ Then there exist $\displaystyle x,y\in X$ such that
$\displaystyle a\,R\,x,\,x\,S\,b,\,b\,R\,y,\,y\,S\,c.$
Then we have $\displaystyle x\,S\circ R\,y$ and since $\displaystyle R\circ S=S\circ R,$ we also have $\displaystyle x\,R\circ S\, y$. There must therefore exist $\displaystyle z\in X$ such that
$\displaystyle x\,R\,z,\,z\,S\,y.$
But then, from the transitivity of R and S, we get
$\displaystyle a\,R\,z,\,z\,S\,c,$
which means that $\displaystyle a\,R\circ S\,c.$
2. If R, S are preorders and their composition is transitive, then they must commute.
Proof. Let $\displaystyle x,y\in X$ and $\displaystyle x\,S\circ R\,y.$ Then there is $\displaystyle b\in X$ such that
$\displaystyle x\,S\,b,\,b\,R\,y.$
Let's take
$\displaystyle a:=x,\,c:=y.$
Then, since R and S are reflexive, we have
$\displaystyle a\,R\,x,\,x\,S\,b,\,b\,R\,y,\,y\,S\,c$
(as we had in the previous proof). Therefore $\displaystyle a\,R\circ S\,b$ and $\displaystyle b\,R\circ S\,c,$ and by transitivity $\displaystyle a\,R\circ S\,c.$ But $\displaystyle a=x$ and $\displaystyle c=y$ so we are done.
3. If If R, S are transitive and their composition is transitive, then they must commute.
I believe this one is false, because the above argument fails to work for it, but that's no proof. I can't think of a way of refuting this statement other than by looking at random examples and hoping for the best. Could you suggest something more systematic? I would also find it very kind if someone would tell me about any embarrassing mistakes I made in my proofs.