Results 1 to 14 of 14

Math Help - Special Relations and Partial Orders help

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    21

    Special Relations and Partial Orders help

    Hi,

    I have the following relation:



    And I need help giving a mathmatical definition of this relation. I am also having problems stating if the relation is reflexive, symmetric, transitive or antisymmetric. I also need to state my reasons for this. Another problem I am having is stating whether this is a partial order or an equivalence relation.

    Any help would be good.

    Thanks in advance if you can help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1
    Any relation is a set of ordered pairs. Reading the directed pseudograph we get the relation \left\{ {\left( {a,a} \right),\left( {b,a} \right),\left( {b,c} \right),\left( {c,a} \right),\left( {c,b} \right)} \right\}.
    Now carry out the tests for the various properties a relation may have.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    21
    Quote Originally Posted by Plato View Post
    Any relation is a set of ordered pairs. Reading the directed pseudograph we get the relation \left\{ {\left( {a,a} \right),\left( {b,a} \right),\left( {b,c} \right),\left( {c,a} \right),\left( {c,b} \right)} \right\}.
    Now carry out the tests for the various properties a relation may have.
    Thanks for your answer, however, I do not understand what you are saying sorry, can you explain it simpler at all?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Mathematically, the relation should consist of pairs of "coordinates" of the form (X,Y), meaning that there is an arrow from X to Y. For example, (A,A) will be one such pair, because there is a loop going from A to A. Another element in the relation will be (B,A), because there is an arrow from B to A. There are five arrows in the picture, so the relation will consist of five such pairs.

    The relation will be reflexive if (X,X) is in the relation for each point X. In terms of arrows, this as the same as saying that there should be a loop from each point to itself.

    It will be symmetric if (Y,X) is in the relation whenever (X,Y) is. In other words, whenever there is an arrow from X to Y there is also an arrow from Y to X.

    It will be transitive if (X,Z) is in the relation whenever (X,Y) and (Y,Z) both are. In other words, if there are arrows from X to Y and from Y to Z, there should also be an arrow going direct from X to Z. (Don't forget to include cases where X, Y and Z are not all different. For example, Z might be the same point as X.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2008
    Posts
    21
    Sorry i've come back to this topic, but I need to make sure i've understood what is being said.

    Going by what you are saying then, is this relation Transitive? Can you explain to me where I have gone wrong, if I have got it wrong please?

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by rushhour View Post
    Going by what you are saying then, is this relation Transitive?
    The relation is not transive.
    To see that, note that (b,c) & (c,b) are both in the relation but not (b,b).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2008
    Posts
    21
    Quote Originally Posted by Plato View Post
    The relation is not transive.
    To see that, note that (b,c) & (c,b) are both in the relation but not (b,b).
    Sorry, I've just noticed a mistake in the picture of the relation, it should read:



    Is it transitive? I'm not very sure on special relations and partial orders, so just need to get some help form members of this forum.

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by rushhour View Post
    Sorry, I've just noticed a mistake in the picture of the relation, it should read:



    Is it transitive?
    In terms of the diagram, transitivity means that whenever you can get from node x to node y in two steps (by going along arrows in the indicated direction), you can also get from x to y in one step.

    For example, you can get from b to a in two steps by first taking one of the arrows from b to c and then taking the arrow from c to a. But there is an arrow going direct from b to a. So for this particular "journey", transitivity applies.

    In fact, you can easily check that the revised diagram (though not the original one) does give a transitive relation. The reason is that there are only a few ways of making a two-step journey. Either you start at b and go to a via c, or you start at any of the three vertices and go to a via the loop at a. In each cases, there is a direct route available.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Dec 2008
    Posts
    21
    So there is transitivity between this relation then? Is it symmetric in any way at all? I know that you have to put symmetry in to these terms, if x is related to y, then y is related to x (x,y) => (y,x). Sorry to be of bother, but I just don't get these meanings.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by rushhour View Post
    Is it symmetric in any way at all? I know that you have to put symmetry in to these terms, if x is related to y, then y is related to x (x,y) => (y,x).
    That's right. In terms of the diagram, symmetry means that if there is an arrow from x to y, then there must also be an arrow from y to x. That clearly is not the case for this diagram.

    While we're about it, reflexivity means that for each node x there must be an arrow from x to itself (in other words, a loop at x). Again, that is not the case for this diagram, because the only node at which there is a loop is a.

    So the diagram defines a relation that is transitive, but not symmetric or reflexive.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Dec 2008
    Posts
    21
    Thanks for you help, just one more thing,Is it not a partial order then as well? Because I know that a partial order must be reflexive, antisymmetric and transitive. I just need to make sure, I've got it right.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member Jason Bourne's Avatar
    Joined
    Nov 2007
    Posts
    132
    Quote Originally Posted by rushhour View Post
    Thanks for you help, just one more thing,Is it not a partial order then as well? Because I know that a partial order must be reflexive, antisymmetric and transitive. I just need to make sure, I've got it right.
    I can't see the link you are posting for some reason but just check if the relation is Anti-Symmetric:

    xRy And yRx \Rightarrow x=y where R is the relation and the notation xRy just means (x,y) \in R
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Dec 2008
    Posts
    21
    I'm guessing its not a partial order because it is not reflexive. This means it can't be an equivalence relation either can it?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member Jason Bourne's Avatar
    Joined
    Nov 2007
    Posts
    132
    Quote Originally Posted by rushhour View Post
    I'm guessing its not a partial order because it is not reflexive. This means it can't be an equivalence relation either can it?
    That is correct.

    It's an equivalence relation on a set X if its:

    Reflexive xRx  \forall x \in X
    Symmetric xRy \Rightarrow yRx \forall x,y \in X
    Transitive xRy, yRz \Rightarrow xRz \forall x,y,z \in X

    A relation on a set X is a partial order if its:

    Reflexive
    Anti - Symmetric
    Transitive
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 02:09 PM
  2. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 6th 2010, 10:33 AM
  3. partial orders
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 07:46 AM
  4. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 2nd 2009, 09:28 PM
  5. Partial orders
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: January 19th 2009, 11:58 AM

Search Tags


/mathhelpforum @mathhelpforum