Results 1 to 5 of 5

Math Help - some statements on composition of relations

  1. #1
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    some statements on composition of relations

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,708
    Thanks
    1638
    Awards
    1

    Re: some statements on composition of relations

    Quote Originally Posted by ymar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: some statements on composition of relations

    Quote Originally Posted by Plato View Post
    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)).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,397
    Thanks
    760

    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.

    i am undecided about 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: some statements on composition of relations

    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Composition of Relations
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 27th 2010, 09:39 AM
  2. Composition of transitive relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2010, 04:41 PM
  3. [SOLVED] Composition of two relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 7th 2009, 09:21 AM
  4. Composition of relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2009, 12:08 PM
  5. composition of relations
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 4th 2009, 08:16 AM

Search Tags


/mathhelpforum @mathhelpforum