Mathematics__POSETS__and__Lattices__Class__Notes

UNIT – 4 POSET and Lattices

Partially Ordered Sets

Consider a relation R on a set S satisfying the following properties:

1. R is reflexive, i.e., xRx for every x ∈ S.
2. R is antisymmetric, i.e., if xRy and yRx, then x = y.
3. R is transitive, i.e., xRy and yRz, then xRz.

Then R is called a partial order relation, and the set S together with partial order is
called a partially order set or POSET and is denoted by (S, ≤).

Example:

1. The set N of natural numbers form a poset under the relation '≤' because
firstly x ≤ x, secondly, if x ≤ y and y ≤ x, then we have x = y and lastly if x ≤ y
and y ≤ z, it implies x ≤ z for all x, y, z ∈ N.
2. The set N of natural numbers under divisibility i.e., 'x divides y' forms a
poset because x/x for every x ∈ N. Also if x/y and y/x, we have x = y. Again if
x/y, y/z we have x/z, for every x, y, z ∈ N.
3. Consider a set S = {1, 2} and power set of S is P(S). The relation of set
inclusion ⊆ is a partial order. Since, for any sets A, B, C in P (S), firstly we
have A ⊆ A, secondly, if A ⊆B and B⊆A, then we have A = B. Lastly, if A ⊆B
and B ⊆C,then A⊆C. Hence, (P(S), ⊆) is a poset.
4. A= {1,2,3,4,6,12,36,48} Relation “ divides”
A is poset, Divides is partial order relation

Hasse diagram: A Hasse diagram is a graphical representation of the relation of
elements of a partially ordered set (poset) with an implied upward orientation.

A point is drawn for each element of the partially ordered set (poset) and joined
with the line segment according to the following rules:

 If p<q in the poset, then the point corresponding to p appears lower in the
drawing than the point corresponding to q.
 The two points p and q will be joined by line segment iff p is related to q.

, Few examples of Hasse Diagram are given below:

Example-1: Draw Hasse diagram for ({3, 4, 12, 24, 48, 72}, /)

Explanation – According to above given question first, we have to find the poset
for the divisibility.
Let the set is A.
A={(3 12), (3 24), (3 48), (3 72), (4 12), (4 24), (4 48), (4 72), (12
24), (12 48), (12 72), (24 48), (24 72)}
So, now the Hasse diagram will be:




In above diagram, 3 and 4 are at same level because they are not related to each
other and they are smaller than other elements in the set. The next succeeding
element for 3 and 4 is 12 i.e, 12 is divisible by both 3 and 4. Then 24 is divisible by
3, 4 and 12. Hence, it is placed above 12. 24 divides both 48 and 72 but 48 does
not divide 72. Hence 48 and 72 are not joined.
We can see transitivity in our diagram as the level is increasing.

Example-2: Draw Hasse diagram for (D , /)

Explanation – Here, D means set of positive integers divisors of 12.
So, D ={1, 2, 3, 4, 6, 12} now the Hasse diagram will be-