Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Partial order relations

  1. Nov 17, 2004 #1
    For some reason I am having a hard time dealing with partial order relations. The definition is what is killing me here. I have a digraph of a partial order relation and yet it does not appear to agree with the definition of partial order. I wish I could draw a picture of the digraph but since that would not work very well I will just do my best to explain it and why I think it is not a partial order.

    R is a relation on X={a,b,c,d,f}

    Starting from the bottom I have

    vertex a which is related to vertex b and vertex c

    Then I have vertex b related to vertex d and c related to vertex d

    then I have vertex d related to vertex d and vertex f

    So correct me if I am wrong but if I were to write out R as a set of ordered pairs I would have

    R={(a,b), (a,c), (b,d), (c,d), (d,f), (d,e)}

    If that is correct then how can this be a partial order when the definition of partial order says a relation is partial order iff R is reflexive? That relation is not reflexive since (a,a) is not an element of R (the same is true for b,c,d,e,f).

    Next problem I have is how to tell if one element is comparable to another. If someone could give me a good intuitive idea of how to tell if two elements of R is comparable I would greatly appericate it.

  2. jcsd
  3. Nov 18, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    it is implicit in the graph that there is a suppressed loop from each point to itself, and that the relation is reflexive, that is a<=a (usually a<a is false....)

    an element is comparable (less than) to another if there is a (directed) path in the graph leading from the smaller to the larger. you are just using transitivity.

    a<b, and b<d so a<d

    a<c and c<d so a<d, good

    a<d and d<f so a<f

    a<d and d<e so a<e

    now do it for b
  4. Nov 18, 2004 #3

    Well now that certainly makes things much easier to deal with.

    b<d and d<f so b<f

    b<d and d<e so b<e

    I appreciate your help matt grime.

    Last edited: Nov 18, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook