For two binary relations R, S on a set X, we define their composition:
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 and for some Then there exist such that
Then we have and since we also have . There must therefore exist such that
But then, from the transitivity of R and S, we get
which means that
2. If R, S are preorders and their composition is transitive, then they must commute.
Proof. Let and Then there is such that
Let's take
Then, since R and S are reflexive, we have
(as we had in the previous proof). Therefore and and by transitivity But and 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.
as far as i can see, your proofs for 1) and 2) are correct, but i see no reason to introduce "a" and "c" in the proof for 2).
by the reflexiveness of R and S, you have xRx and ySy, and so xRSb and bRSy, thus xRSy.
i am undecided about 3.