Discrete Mathematics

Least Upper Bounds And Latest Lower Bounds In A Lattice

Least Upper Bounds and Latest Lower Bounds in a Lattice

Let (L, ∨ , ∧ ) be a lattice and let a, b ∈ L. We now show that LUB of {a, b} ∈ L with respect to the partial order introduced above is a ∨ b and GLB of {a, b} is a ∧ b.

From absorption law
a ∧ (a ∨ b) = a
b ∧ (a ∨ b) = b

Therefore a ≤ a ∨ b and b ≤ a ∨ b, showing that a ∨ b is upper bound for {a, b}. Suppose that there exists c Î L such that a ≤c, b ≤ c. Thus we have
a ∨ c = c and b ∨ c = c
and then
(a ∨ b) ∨ c = a ∨ (b ∨ c) = a ∨ c = c ,

implying that a ∨ b ≤ c. Hence a ∨ b is the least upper bound of a and b.

Similarly, we can show that a ∧ b is GLB of a and b.

The above discussion shows that the two definitions of lattice given so far are equivalent.

Example: Let  be collection of sets with binary operations Union and Intersection of sets. Then ( , ∪, ∩) is a lattice. In this lattice, the partial order relation is set inclusion. In fact, for A, B ∈


For example, the diagram of lattice of subsets of {a, b} is