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

Order Relation

  1. May 3, 2005 #1
    How do I verify that R={(1,1). (2,2), (3,3) (3,2) (3,1), (2,1)} is an order relation on {1,2,3}.

    So far, I have that an ordered set is a pair (X, <) where X is a set tand where < in a binary relation on X so that the following three properties are fulfilled:

    1. reflexive prop
    2. anti-symmetric prop
    3. transitive prop

    Do I have to prove each property for R?
     
  2. jcsd
  3. May 3, 2005 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, and the simplest way to check is just go through the pairs.

    Reflexive: Are (1,1), (2,2), (3,3) in the set?

    Anti-symmetric: (2, 1) is in the set. If this relation is anti-symmetric, (1, 2) must not be in the set. Is that true? What other pairs do you have to look at?

    Transitive: I see (3,2) and (2,1) in the set. If this relation is transitive, what pair must be in the set? Is it?
     
  4. May 3, 2005 #3
    Reflexive: (1,1), (2,2), (3,3) are in the set.

    Anti-symmetric: (2, 1) is in the set. If this relation is anti-symmetric, (1, 2) must not be in the set. Yes this is true. So, this property is true.

    Transitive: (3,2) and (2,1) are in the set. If this relation is transitive, then (3,1) must be in the set.

    Follow up:

    Let x,y be in R.

    If y precedes x if and only if y less than or equal to x, the, do I verify that this statement is an order relation like before using the three properties? If I use the three properties, then how can I prove that y precedes x.

    This is how I started off:

    Reflexive Property:
    If x in an element in R, then x < x for all x in R. Therefore, x precedes x.

    Anti-symmetric:
    For all x,y in R if x<y y< x then, x=y, where y precedes x.

    Thank you for your help.
     
    Last edited: May 3, 2005
  5. May 4, 2005 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I was giving an example! (2,1) is not the only pair you need to check.

    You mean x<= x (or [itex]x\le x[/tex]), of course.
     
  6. May 4, 2005 #5

    honestrosewater

    User Avatar
    Gold Member

    I can't really follow what you're saying. You have two order relations here: R and <. And you've defined R to be <. So you really have nothing to prove- just check your definition of < - is it an order relation?
    Did you want to prove something else? You haven't said on what set the relations are defined, but assume they're defined on {1, 2, 3}. Using the usual definition of <, "y precedes x if and only if y less than or equal to x" means "if y precedes x, then y < x" and "if y < x, then y precedes x". So R = {(1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3)}. Is this what you meant to say?
    I think you only meant "For all x and y in R, if (y, x) is in R, then y < x." That also means if y > x, then (y, x) is not in R. Is that what you wanted?
     
  7. May 4, 2005 #6
    This is actually unrelated to the previous problem. But, I think that I have to go through the three properties of an order relation to prove this.

    The problem:

    Let x,y is an element in R, real number. We define a relation <= (precedes symbol) on R. Verify that <= (precedes symbol) defined by

    x<= (precedes) y if and only if y<= x (less than or equal to)

    Verify that <= (precedes symbol) is an order relation.
     
    Last edited: May 4, 2005
  8. May 4, 2005 #7
    Similarly, (3,2) and (3,1) are also anti-symmetric since (2,3) and (1,3) are not on the set, right?
     
  9. May 5, 2005 #8

    honestrosewater

    User Avatar
    Gold Member

    Okay, you said before that y precedes x iff y < x. Let P denote the relation "precedes" and L denote the relation "less than or equal to". So now instead of P = L, you have that (x, y) is in P iff (y, x) is in L. In other words,
    P = {(x, y) : (y, x) is in L and x and y are in R}.
    What else does P equal (what is the relationship between P and L)?
     
  10. May 5, 2005 #9
    Do you mean this relationship?

    P={(x,y): x P y if y L x}

    or do I have to jump into the reflexive property?
     
  11. May 5, 2005 #10

    honestrosewater

    User Avatar
    Gold Member

    I mean that P and L are inverses. Remember that binary relations are sets of pairs. You're told that if (x, y) is in L, then (y, x) is in P, and if (y, x) is in P, then (x, y) is in L. In other words, L and P contain the same pairs- just reversed. If (x, x) is in L, then (x, x) is in P. If (x, y) and (y, z) are in L, then (y, x) and (z, y) are in P.
    In order to prove that P is an order relation, you need to know that L is an order relation. Otherwise, you could only prove that if L is an order relation, then P is an order relation. But assume you already know L is an order relation. Then the following holds:
    For all x, y, and z in R
    1) (x, x) is in L.
    2) If (x, y) and (y, x) are in L, then x = y.
    3) If (x, y) and (y, z) are in L, then (x, z) is in L.
    L and P have the same pairs- just reversed, so:
    For all x, y, and z in R
    4) (x, x) is in P.
    Can you see the rest now? To see the rest, highlight:
    5) If (y, x) and (x, y) are in P, then y = x.
    6) If (y, x) and (z, y) are in P, then (z, x) is in P.
    To make it even clearer, (6) can be rewritten as
    7) If (z, y) and (y, x) are in P, then (z, x) is in P.
    So (4), (5), and (7) show that P is an order relation. Notice that P is usually called "greater than or equal to" :)

    Does that make sense?
     
  12. May 5, 2005 #11
    Yes, it makes sense. I got confused with the "precedes" symbol, when in reality it somewhat refers closely to the "less than or equal to" sign. Thank you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Order Relation
  1. Order types (Replies: 4)

Loading...