Thread: some statements on composition of relations

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.

Originally Posted by ymar

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$

Are you very sure that you given the same definition as you text/author?
There a few authors who do use that definition.

However, most use the following:
$\displaystyle R\circ S=\left\{(x,y)\in X\,|\,(\exists c\in X)\,xSc\,\wedge\,cRy\}\right$
i.e. reading right to left as in function composition.

Originally Posted by Plato

Are you very sure that you given the same definition as you text/author?
There a few authors who do use that definition.

However, most use the following:
$\displaystyle R\circ S=\left\{(x,y)\in X\,|\,(\exists c\in X)\,xSc\,\wedge\,cRy\}\right$
i.e. reading right to left as in function composition.

These statements aren't from any book. It's what I've been thinking about. Yes, definitions vary but my knowledge of the concept comes from semigroup theory where my definition prevails (together with writing xf instead of f(x)).

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.

Originally Posted by Deveno

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.

You're right. I introduced them only to show how the second proof is similar to the first. This is how I came up with it -- by "inverting" (please don't make me think what I mean by this) the first one.