Mathematical Foundation of Computer Science

DHARM

152 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Thus, a simplified poset will be,

≤ = {(2, 4), (2, 6), (3, 6), (4, 8), (6, 24), (8, 24)}

and there graphical representation is shown below in Fig. 6.1.

24

6

(^23)
4
8
Fig. 6.1
To simplify further, since all arrows pointed in one direction (upward) so, we can omit
the arrows. Such a graphical representation of a partial ordered relation in which all arrow
heads are understood (to be pointed upward) is called Hasse diagram of the relation shown in
Fig. 6.2.
24
6
2 3
4
8
Fig. 6.2 Hasse diagram.
Example 6.2. Let set X = {α, β, γ } then draw the Hasse diagram for the poset (P(X), ⊆).
Sol. The P(x) is the power set of X. So we have,
P(X) = {Ø, {α}, {β}, {γ}, {α, β}, {β, γ}, {α, γ}, {α, β, γ}}
Therefore, the vertices in the Hasse diagram will corresponds to all elements of P(X)
and the edges are constructed according to the partial ordered relation inclusion (⊆) which are
given as,
⊆ = {(Ø, {α}), (Ø, {β}), (Ø, {γ}), ({α}, {α, β}), ({α}, {α, γ}), ({β}, {α, β}), ({β}, {β, γ}), ({γ}, {α, γ}),
({γ}, {β, γ}), ({α, β},{α, β, ?}), ({β, γ}, {α, β, γ}), ({α, γ}, {α, β, γ})}.