# Hasse Diagram

• Apr 10th 2009, 08:46 AM
SirIvy07
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.
• Apr 10th 2009, 11:03 AM
Moo
Hello,
Quote:

Originally Posted by SirIvy07
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

Quote:

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.
• Apr 10th 2009, 11:34 AM
Opalg
Quote:

Originally Posted by SirIvy07
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)
• Apr 10th 2009, 11:43 AM
Moo
Quote:

Originally Posted by Opalg
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 (Headbang)
• Apr 10th 2009, 01:03 PM
SirIvy07
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!
• Apr 10th 2009, 01:35 PM
Plato
Quote:

Originally Posted by SirIvy07
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.
• Apr 10th 2009, 01:53 PM
SirIvy07
Ah Okay I see where I went wrong.