Results 1 to 7 of 7

Math Help - Hasse Diagram

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    9

    Hasse Diagram

    Here is the question.

    Let S={1,2,3,4}. With respect to the lexicographic order based on theusual less than relation:

    a)find all pairs in S x S less than (2,3)

    ans: (1,1),(1,2),(1,3),(1,4),(2,1),(2,2)

    b) all pairs in S x S greater than (3,1)

    ans: (3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)

    c) draw the Hasse Diagram of poset (SxS,≼)

    I understand posets and Hasse Diagrams but I am having a hard time visualizing part c.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by SirIvy07 View Post
    Here is the question.

    Let S={1,2,3,4}. With respect to the lexicographic order based on theusual less than relation:

    a)find all pairs in S x S less than (2,3)

    ans: (1,1),(1,2),(1,3),(1,4),(2,1),(2,2)

    b) all pairs in S x S greater than (3,1)

    ans: (3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)
    okay

    c) draw the Hasse Diagram of poset (SxS,≼)

    I understand posets and Hasse Diagrams but I am having a hard time visualizing part c.
    Well, here is the example in wikipedia Partially ordered set - Wikipedia, the free encyclopedia (the pic to the right)
    But yours is much easier, since there is a single relationship between each couple.

    (1,1)<(1,2)<(1,3)<(1,4)<(2,1)<(2,2)<...<(4,3)<(4,4 )

    Each < is symbolized by an arrow.
    Last edited by Moo; April 10th 2009 at 11:43 AM. Reason: woops
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by SirIvy07 View Post
    Here is the question.

    Let S={1,2,3,4}. With respect to the lexicographic order based on the usual less than relation:

    a)find all pairs in S x S less than (2,3)

    ans: (1,1),(1,2),(1,3),(1,4),(2,1),(2,2)

    b) all pairs in S x S greater than (3,1)

    ans: (3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)

    c) draw the Hasse Diagram of poset (SxS,≼)

    I understand posets and Hasse Diagrams but I am having a hard time visualizing part c.
    (The answers to a) and b) are correct.)

    The lexicographic order is a total order. As Moo commented, the ordering is

    (1,1)<(1,2)<(1,3)<(1,4)<(2,1)<(2,2)<...<(4,3)<(4,4 ).

    In a Hasse diagram, you only need to connect each element to its immediate successor. So put all 16 elements in a line, starting with (1,1) and going up to (4,4), and draw a line from each element to its successor.
    Code:
      o------o------o------o------o------o--- ... ---o------o 
    (1,1)  (1,2)  (1,3)  (1,4)  (2,1)  (2,2)  ...  (4,3)  (4,4)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by Opalg View Post
    In a Hasse diagram, you only need to connect each element to its immediate successor. So put all 16 elements in a line, starting with (1,1) and going up to (4,4), and draw a line from each element to its successor.
    Code:
      o------o------o------o------o------o--- ... ---o------o 
    (1,1)  (1,2)  (1,3)  (1,4)  (2,1)  (2,2)  ...  (4,3)  (4,4)
    I don't know what happened, I had this one in mind and then just thought it couldn't be the correct Hasse diagram
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    9
    Okay I know how to draw a hasse diagram. I was misinterpreting (SxS,<).

    I may be mistaken but the diagrams you two have provided don't seem to be posets. For example they seem to fail the antisymmetric requirement in that there is (1,2) and (2,1) present.

    So I'm thinking the diagram of the poset is

    (1,1)--(1,2)--(1,3)--(1,4)--(2,2)--(2,3)--(2,4)--(3,3)--(3,4)

    Thanks for the input!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,648
    Thanks
    1596
    Awards
    1
    Quote Originally Posted by SirIvy07 View Post
    I may be mistaken but the diagrams you two have provided don't seem to be posets. For example they seem to fail the antisymmetric requirement in that there is (1,2) and (2,1) present.
    You must not think of the pairs (1,2)~\&~(2,1) as pairs in the relation. They are not.
    The pair \left( {(1,2),(2,1)} \right) of pairs belongs to the relation.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2009
    Posts
    9
    Ah Okay I see where I went wrong.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. please help for Hasse diagram
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 20th 2009, 11:18 AM
  2. Hasse diagram
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 26th 2009, 10:47 PM
  3. Hasse Diagram
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2009, 08:41 PM
  4. Hasse diagram ?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 16th 2008, 01:21 AM
  5. Hasse Diagram
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: March 7th 2007, 09:45 PM

Search Tags


/mathhelpforum @mathhelpforum