Results 1 to 14 of 14

Math Help - Partially ordered set.

  1. #1
    Member
    Joined
    May 2008
    Posts
    140

    Partially ordered set.

    Let X be a set with a binary operation p: X x X -->X,
    abbreviated to p(x,y)=xy. Suppose p satisfies

    1) x(yz)=(xy)z
    2) xy=yx
    3) xx=x

    for all x, y, z in X. Define < on X by

    x<y iff xy=y.

    Prove that

    a) (X,<) is a partially ordered set.

    b) Each pair of elements has a least upper bound. That is, given x, y in X, there is a z in X, such that x<z, y<z, and if w in X is such that x<w, y<w, then z<w.


    PLEASE HELP!!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by Cairo View Post
    Let X be a set with a binary operation p: X x X -->X,
    abbreviated to p(x,y)=xy. Suppose p satisfies

    1) x(yz)=(xy)z
    2) xy=yx
    3) xx=x

    for all x, y, z in X. Define < on X by

    x<y iff xy=y.

    Prove that

    a) (X,<) is a partially ordered set.

    b) Each pair of elements has a least upper bound. That is, given x, y in X, there is a z in X, such that x<z, y<z, and if w in X is such that x<w, y<w, then z<w.


    PLEASE HELP!!!!
    Does it satisfy the three conditions (reflexive, antisymmetric, and transitive)? For example 2) tells you something about symmetry...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    140
    I'm not sure what you mean here.

    This is all that is stated in the question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Cairo View Post
    I'm not sure what you mean here.

    This is all that is stated in the question.
    Do you know what a partial ordering is?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    140
    A partial ordering is reflexive, transitive and antisymmetric.

    Is (1) showing transitivity, (2) showing antisymmetric and (3) showing reflexivity?

    I'm not sure how to proceed from here!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    What you need is to take the definition of reflexivity and substitute the definition of < there. You will get an equation. See if you can derive that equation from the three given equations. If you are able, then < is reflexive.

    By the way, it seems to me that (X, <) is indeed a non-strict (or reflexive, or weak) partial order. While in mathematics one can use any notation as long as one explains what exactly it means, it is better to use suggestive notations. (E.g., the set of functions from A to B is sometimes denoted B^A to remind that the size of this set is |B|^{|A|}.) Here, it is better to denote the relation with <= because in regular use, < means strict, or irreflexive, order.

    If you need an intuitive illustration, you can think of X as a family of sets, the binary operation as intersection and the order as the subset relation.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    (1) showing transitivity:
    you need to show that if x<y,y<z,then x<z.
    (2) showing antisymmetric:
    you need to show that if x<y, and y<x, then x and y are the same elements.
    (3) showing reflexivity:
    you need to show that: x<x for all x in X.
    for (b), the existence of upper bound: take z=xy.
    Actually, xy is the least upper bound of x and y. I leave it to you to prove this statement.
    Hint: you need to prove If x<w, y<w, then xy<w.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2008
    Posts
    140
    Ok...

    So my proof starts

    Since xx=x (by 3), x<x for each x in X and so is reflexive.

    Since xy=y=yx (by 2), then x=y and is antisymmetric.

    I'm lost when it comes to transitivity....

    I thought

    If x<y and y<z, then xy=y and yz=z, so x<z is xyyz=xyz (by 3) but then get in a mess!

    Is any of this right?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1609
    Awards
    1
    Quote Originally Posted by Cairo View Post
    Ok...

    So my proof starts

    Since xx=x (by 3), x<x for each x in X and so is reflexive.

    Since xy=y=yx (by 2), then x=y and is antisymmetric.

    I'm lost when it comes to transitivity....

    I thought

    If x<y and y<z, then xy=y and yz=z, so x<z is xyyz=xyz=xz (by 3)
    Is any of this right?
    You are done.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2008
    Posts
    140
    Sometimes it is difficult to see the wood through the trees!

    Thanks for this Plato.

    Now that I have the bones of the proof, can anybody offer a way to make it look more elegant?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    May 2008
    Posts
    140
    My proof

    A partial order on a set X is a reflexive, antisymmetric and transitive relation.
    For all x in X, we have xx=x (by 3), and so x<x. Therefore < is reflexive.
    If x<y and y<x, then by definition xy=yx=y (by 2). That is x=y and so < is antisymmetric.
    If x<y and y<z, then by definition of < we have xy=y and yz=z.
    Now, xyyz=x(yy)z=xyz=xz (by 1 and 3). Hence, x<z, and < is transitive.
    Since < is reflexive, antisymmetric and transitive, < is a partial order on X.
    That is (X,<) is a partially ordered set.

    I'not entirely convinced the proof is correct. Firstly, the domain is the Cartesian product, so should my proof start with
    for all (x,x) in X x X, we have xx=x (by 3), and so x<x ?
    I'm also not comfortable with transitivity. I have shown that xyyz=xz, but surely x<z should be xz=z. have I missed something here?
    Finally, what do people think of the way the proof is set out? Could it be tidied up in any way?
    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1609
    Awards
    1
    If x<y~\&~y<z we know that xy=y~\&~yz=z.
    It follows that xz=x(yz)=(xy)z=yz=z.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    May 2008
    Posts
    140
    Thanks Plato.

    Does the rest follow OK? I ask, because this year we have been told that full credit will only be awarded if both the soultion is correct, aswell as being carefully and logically presented.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    May 2008
    Posts
    140
    To prove the second part of the question.

    Let z=xy in X, for x,y in X.

    Then, x<z implies x(xy)=xy implies (xx)y=xy implies xy=xy.

    Also, y<z implies y(xy)=xy implies (yx)y=xy implies (xy)y=xy implies x(yy)=xy implies xy=xy.

    Now, if w in X, and x<w implies xw=w, and y<w implies yw=w, then z<w implies (xy)w=w implies x(yw)=w implies xw=w implies w=w.

    Hence, each pair of elements has a least upper bound.

    Is this even remotely correct?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Q's on Partially Ordered Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 5th 2011, 01:17 AM
  2. Question about partially ordered sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 6th 2011, 12:54 PM
  3. Partially ordered set with no maximal element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 12:37 AM
  4. Replies: 7
    Last Post: February 25th 2010, 04:44 AM
  5. Partially Ordered Set, example from Wiki.
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 18th 2010, 07:58 PM

Search Tags


/mathhelpforum @mathhelpforum