some statements on composition of relations

**ymar** · Sep 29th 2011, 04:19 AM

For two binary relations R, S on a set X, we define their composition:

$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 $a\,R\circ S\,b$ and $b\,R\circ S\,c$ for some $a,b,c\in X.$ Then there exist $x,y\in X$ such that

$a\,R\,x,\,x\,S\,b,\,b\,R\,y,\,y\,S\,c.$

Then we have $x\,S\circ R\,y$ and since $R\circ S=S\circ R,$ we also have $x\,R\circ S\, y$ . There must therefore exist $z\in X$ such that

$x\,R\,z,\,z\,S\,y.$

But then, from the transitivity of R and S, we get

$a\,R\,z,\,z\,S\,c,$

which means that $a\,R\circ S\,c.$

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

Proof. Let $x,y\in X$ and $x\,S\circ R\,y.$ Then there is $b\in X$ such that

$x\,S\,b,\,b\,R\,y.$

Let's take

$a:=x,\,c:=y.$

Then, since R and S are reflexive, we have

$a\,R\,x,\,x\,S\,b,\,b\,R\,y,\,y\,S\,c$

(as we had in the previous proof). Therefore $a\,R\circ S\,b$ and $b\,R\circ S\,c,$ and by transitivity $a\,R\circ S\,c.$ But $a=x$ and $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.

**Plato** · Sep 29th 2011, 04:38 AM

Originally Posted by ymar

For two binary relations R, S on a set X, we define their composition:
$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:
$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.

**ymar** · Sep 29th 2011, 04:51 AM

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

**Deveno** · Sep 29th 2011, 05:14 AM

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.

**ymar** · Sep 29th 2011, 05:20 AM

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.

Thread: some statements on composition of relations

LinkBack

Thread Tools

Display

some statements on composition of relations

Re: some statements on composition of relations

Re: some statements on composition of relations

Re: some statements on composition of relations

Re: some statements on composition of relations

Similar Math Help Forum Discussions

Composition of Relations

Composition of transitive relations

[SOLVED] Composition of two relations

Composition of relations

composition of relations

Search Tags