Mathematical Foundation of Computer Science

DHARM

156 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

{α, β}}. Then, poset (P(X), ⊆) in which each pair have a unique LUB & a unique GLB e.g.
for the pair ({α, β}, {β}) meet and join will be,
GLB ({α, β}, {β}) = {α, β} ∧ {β} ⇒ {α, β} ∩ {β} = {β}
LUB ({α, β}, {β}) = {α, β} ∨ {β} ⇒ {α, β} ∪ {β} = {α, β}
(Reader can also verify these results from the Hasse diagram shown in Fig. 6.3)
Similarly we can determine the LUB & GLB for every pair of the poset (P(X), ⊆) that are
listed in table shown in Fig. 6.5.

GLB Ø {ααααα}{βββββ}{ααααα, βββββ}

Ø ØØØ Ø

{ααααα} Ø{α}Ø {α}

{βββββ} ØØ{β}{β}

{ααααα, βββββ} Ø{α}{β}{α, β}

LUB Ø {ααααα}{βββββ}{ααααα, βββββ}

Ø Ø{α}{β}{α, β}

{ααααα} {α}{α}{α, β}{α, β}

{βββββ} {β}{α, β}{β}{α, β}

{ααααα, βββββ} {α, β}{α, β}{α, β}{α, β}

Fig. 6.5
Example 6.5. Consider the poset (I+, ≤) where I+ is the set of positive integers and the partial
ordered relation ≤ is defined as i.e. if x and y ∈ I+ then x ≤ y means ‘x divides y’. Then poset (I+,
≤) is a lattice. Because,
GLB(x, y) = x ∧ y = lcm(x, y)[lcm: least common divisor]
and LUB(x, y) = x ∨ y = gcd(x, y)[gcd: greatest common divisor]
Example 6.6. Let R be the set of real numbers in [0, 1] and the relation ‘≤’ be defined as ‘less
than or equal to’ over the set R, then poset (R, ≤) is a lattice. Assume r 1 and r 2 are the elements
∈ R s.t. 0 ≤ r 1 , r 2 ≤ 1 then meet and join are given by,
GLB(r 1 , r 2 ) = r 1 ∧ r 2 = Min(r 1 , r 2 )
and LUB(r 1 , r 2 ) = r 1 ∨ r 2 = Max(r 1 , r 2 )
In the next section we will discuss the theorems that shows the relationship between
the partial ordered relation ‘≤’ and the binary operations GLB & LUB in a lattice (X, ≤).
Theorem 6.4.1. Let (X, ≤) be a lattice, then for any x, y ∈ X,
(i) x ≤ y ⇔ GLB(x, y) = x
and, (ii) x ≤ y ⇔ LUB(x, y) = y
Proof. (Immediately follows from the definition of GLB and LUB)
Assume x ≤ y, since we know that x ≤ x ⇒ x ≤ GLB(x, y).