# Thread: some statements on composition of relations

1. ## 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.

2. ## Re: some statements on composition of relations

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.

3. ## Re: some statements on composition of relations

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

4. ## Re: some statements on composition of relations

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.