Results 1 to 11 of 11

Math Help - Partial order relation

  1. #1
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340

    Partial order relation

    I need to show that relation R is partial order relation.
    R = \{ (a,a),(b,b),(c,c),(a,b),(a,c),(b,c)\}

    I see that it is reflexive and transitive, but I don't see that is antisymmetric.

    In the book stands that it is antisymmetric because
    (a,b) \in R \wedge (b,a) \notin R, (a,c) \in R \wedge (c,a) \notin R,(b,c) \in R \wedge (c,b) \notin R

    Can someone explain me this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by OReilly
    I need to show that relation R is partial order relation.
    R = \{ (a,a),(b,b),(c,c),(a,b),(a,c),(b,c)\}

    I see that it is reflexive and transitive, but I don't see that is antisymmetric.

    In the book stands that it is antisymmetric because
    (a,b) \in R \wedge (b,a) \notin R, (a,c) \in R \wedge (c,a) \notin R,(b,c) \in R \wedge (c,b) \notin R

    Can someone explain me this?
    Since there are no elemets such as,
    x\leq y and y\leq x thus, x\not =y
    The anti-symettric property is never violated.

    By the anti-symettric property we do not mean to say you can find such elements but rather if they exist then they are equal.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    Since there are no elemets such as,
    x\leq y and y\leq x thus, x\not =y
    The anti-symettric property is never violated.

    By the anti-symettric property we do not mean to say you can find such elements but rather if they exist then they are equal.
    I don't understand. Can explain it a little bit more?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by OReilly
    I don't understand. Can explain it a little bit more?
    By x\leq y I mean xRy.

    Thus by antisymettry we have that if, for all
    x\leq y and y\leq x then, x=y.
    The antisymettric property would be violated if, there exists
    x\leq y and y\leq x the, x\not = y
    But notice that the latter never happens because the, pairs,
    (b,a), (c,a), (c,b) are not elements of \leq .
    Thus, the antisymmetric propetry is never violated and thus this ordering relation is antisymettric.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    By x\leq y I mean xRy.

    Thus by antisymettry we have that if, for all
    x\leq y and y\leq x then, x=y.
    The antisymettric property would be violated if, there exists
    x\leq y and y\leq x the, x\not = y
    But notice that the latter never happens because the, pairs,
    (b,a), (c,a), (c,b) are not elements of \leq .
    Thus, the antisymmetric propetry is never violated and thus this ordering relation is antisymettric.
    Well, I still don't understand anti-symmetric property.

    For example: relation R = \{ (a,a),(b,b),(c,c)\} is reflexive, symmetric and transitive.

    Is it anti-symmetric?
    Last edited by OReilly; April 17th 2006 at 05:37 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    Yes. To violate the anti-symmetry property you have to have x and y such that x \not= y and (x,y) \in R and (y,x) \in R. The relation R = \{ (a,a), (b,b), (c,c) \} has no such pair.

    You may find it easier to work in terms of a strict partial order, which has the properties of being transitive, never reflexive (contains no (x,x)) and antisymmetric (never contains both (x,y) and (y,x)). The difference is that a weak order contains all pairs (a,a), a strict order contains none of them.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I have a feeling OReilly is gonna learn Zorn's Lemma soon.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Another way to look at it is in logic a conditional statement is only fasle when the "if" part is true and "then" part is false. Otherwise it is always true. Thus when the "if" part is always "false" it does not matter what the "then" part is, it must be true. Thus, over here no matter what two ordered pairs you take the "if" part for the anti-symettric property is always false because there are no such paris in opposites. Thus, the anti-symettric property is always true here.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Well, I think I understood it, but still don't feel it!

    Let me show another example of relation:
    <br />
R = \{ (a,a),(b,b),(c,c),(a,b)\}<br />

    This relation is reflexive and transitive.

    It is not symmetric since there is no pair (b,a).
    But it is anti-symmetric because pair (a,b) doesn't have pair (b,a) to which could be compared for anti-symmetric property (if it would have it would be actually symmetric) and since all other pairs are anti-symmetric then whole R is anti-symmetric.

    I think I understand whole concept, but I am not comfortable with it.

    By the way, what is Zorn's Lemma?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by OReilly
    Well, I think I understood it, but still don't feel it!

    Let me show another example of relation:
    <br />
R = \{ (a,a),(b,b),(c,c),(a,b)\}<br />

    This relation is reflexive and transitive.

    It is not symmetric since there is no pair (b,a).
    But it is anti-symmetric because pair (a,b) doesn't have pair (b,a) to which could be compared for anti-symmetric property (if it would have it would be actually symmetric) and since all other pairs are anti-symmetric then whole R is anti-symmetric.
    Good

    Quote Originally Posted by OReilly
    I think I understand whole concept, but I am not comfortable with it.
    Many people are not because it is pure math

    Quote Originally Posted by OReilly
    By the way, what is Zorn's Lemma?
    One of the most useful tools in mathematics.

    In a partially ordered set no need be that two elements are always comparable. Meaning not related to each other. A chain is a subset of the partially ordered set such as any two elements are comparable to eachother. Another was of looking at the chain as a subset of the ordering relation because everything in an ordering relation is comparable and only those elements can be related to its other elements.

    A upper bound of a chain x\in R is an element such as aRx for all elements in the chain.

    Zorn's Lemma states that in a partially ordered set such as every chain has an upper bound there exists a maximal element x. Meaning If xRs then x=s.
    ---------
    Why is it useful?
    For example, without it we would never have Analysis. Because in analysis the fundamental property of real numbers is that if there exists a increasing sequence having an upper bound then it must have a minimal upper bound. This is almost the very definition of Zorn's Lemma.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    One of the most useful tools in mathematics.

    In a partially ordered set no need be that two elements are always comparable. Meaning not related to each other. A chain is a subset of the partially ordered set such as any two elements are comparable to eachother. Another was of looking at the chain as a subset of the ordering relation because everything in an ordering relation is comparable and only those elements can be related to its other elements.

    A upper bound of a chain x\in R is an element such as aRx for all elements in the chain.

    Zorn's Lemma states that in a partially ordered set such as every chain has an upper bound there exists a maximal element x. Meaning If xRs then x=s.
    ---------
    Why is it useful?
    For example, without it we would never have Analysis. Because in analysis the fundamental property of real numbers is that if there exists a increasing sequence having an upper bound then it must have a minimal upper bound. This is almost the very definition of Zorn's Lemma.
    You have killed me now!

    I am still far, far away of understanding that...
    Hopefully, I will get there (I know i will)!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 3rd Order Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 26th 2011, 03:44 AM
  2. Partial Order Relation help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2011, 12:29 AM
  3. Partial Order relation and hasse diagram mxa/min
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 27th 2010, 11:02 PM
  4. Second Order Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 12th 2008, 01:59 PM
  5. Order/Relation Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2006, 09:51 AM

Search Tags


/mathhelpforum @mathhelpforum