Hasse Diagrams
A Hasse diagram is a graphical rendering of a partially ordered set
displayed via the cover relation of the POSET with an implied upward
orientation. A point is drawn for each element of the poset, and line
segments are drawn between these points according to the following
two rules:
1. If x< y in the poset, then the point corresponding to x appears lower
in the drawing than the point corresponding to y.
2. The line segment between the points corresponding to any two
elements x and y of the poset is included in the drawing iff x covers y
or y covers x.
Hasse diagrams are also called upward drawings.
1
Hasse Diagrams
Given any partial order relation defined on a finite set,
it is possible to draw the directed graph so that all
of these properties are satisfied.
Remove self loop and transitive edge.
This makes it possible to associate a somewhat simpler
graph, called a Hasse diagram, with a partial order
relation defined on a finite set.
2
Hasse Diagram
• For the poset ({1,2,3,4,6,8,12}, |)
3
4
Maximal and Minimal Elements
a is a maximal in the poset (S, ) if there is no b S
such that a b. Similarly, an element of a poset is
called minimal if it is not greater than any element of
the poset. That is, a is minimal if there is no element
b S such that b a.
It is possible to have
multiple minimals and maximals.
5
6
7
8
9
Greatest Element and Least Element
a is the greatest element in the poset (S, ) if b a
for all b S . Similarly, an element of a poset is called
the least element if it is less or equal than all other
elements in the poset. That is, a is the least element if
a b for all b S
10
Upper bound, Lower bound
Sometimes it is possible to find an element that is
greater than all the elements in a subset A of a poset
(S, ). If u is an element of S such that a u for all
elements a A , then u is called an upper bound of A.
Likewise, there may be an element less than all the
elements in A. If l is an element of S such that l a
for all elements a A , then l is called a lower bound of
A.
11
Upper Bound of:
ub{2,6}={6,12}
ub{4,8}={8}
ub{2,6}= {6,12}
Ub{3,4}={12}
Ub{8,12}= no upper bound
Ub{2,3,6}={6,12}
Ub{1,2,4}={4,8,12}
Lower Bounds:
lb{2,6}={1,2}
lb{4,8}={1,2,4}
lb{3,4}={1}
lb{8,12}= {4,2,1}
lb{2,3,6}={1}
lb{1,2,4}={1,2}
12
Least Upper Bound,
Greatest Lower Bound
The element x is called the least upper bound (lub) of
the subset A if x is an upper bound that is less than
every other upper bound of A.
The element y is called the greatest lower bound (glb)
of A if y is a lower bound of A and z y whenever z is
a lower bound of A.
13
Upper Bound and least upper bound of:
ub{2,6}={6,12} lub{2,6}={6}
ub{4,8}={8} lub{4,8}={8}
ub{2,6}= {6,12}
Ub{3,4}={12}
Ub{8,12}= no upper bound
Ub{2,3,6}={6,12} lub{2,3,6}={6}
Ub{1,2,4}={4,8,12} lub{1,2,4}={4}
Lower Bounds and greatest lower
bounds:
lb{2,6}={1,2} glb{2,6}={2}
lb{4,8}={1,2,4} glb{4,8}={4}
lb{3,4}={1} glb{3,4}={1}
lb{8,12}= {4,2,1} glb{8,12}={4}
lb{2,3,6}={1} glb{2,3,6}={1}
lb{1,2,4}={1,2}
14
15
16
Lattices
A partially ordered set in which every pair
of elements has both a least upper bound
and a greatest lower bound is called a
lattice.
17
Examples 21 and 22, p. 575 in Rosen.
18
