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.$

If R, S are preorders and their composition is transitive, then they must commute.

2.

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.