Page 647 - Discrete Mathematics and Its Applications

626 9 / Relations

EXAMPLE 19 Find the greatest lower bound and the least upper bound of {b, d, g}, if they exist, in the poset
shown in Figure 7.

Solution: The upper bounds of {b, d, g} are g and h. Because g ≺ h, g is the least upper bound.
The lower bounds of {b, d, g} are a and b. Because a ≺ b, b is the greatest lower bound. ▲

EXAMPLE 20 Find the greatest lower bound and the least upper bound of the sets {3, 9, 12} and {1, 2, 4, 5, 10},
if they exist, in the poset (Z , |).
+
Solution: An integer is a lower bound of {3, 9, 12} if 3, 9, and 12 are divisible by this integer.
The only such integers are 1 and 3. Because 1 | 3, 3 is the greatest lower bound of {3, 9, 12}.
The only lower bound for the set {1, 2, 4, 5, 10} with respect to | is the element 1. Hence, 1 is
the greatest lower bound for {1, 2, 4, 5, 10}.
An integer is an upper bound for {3, 9, 12} if and only if it is divisible by 3, 9, and 12.
The integers with this property are those divisible by the least common multiple of 3, 9, and
12, which is 36. Hence, 36 is the least upper bound of {3, 9, 12}. A positive integer is an upper
bound for the set {1, 2, 4, 5, 10} if and only if it is divisible by 1, 2, 4, 5, and 10. The integers
with this property are those integers divisible by the least common multiple of these integers,
which is 20. Hence, 20 is the least upper bound of {1, 2, 4, 5, 10}. ▲

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. Lattices have many special properties. Furthermore,
lattices are used in many different applications such as models of information flow and play an
important role in Boolean algebra.

EXAMPLE 21 Determine whether the posets represented by each of the Hasse diagrams in Figure 8 are lattices.

Solution: The posets represented by the Hasse diagrams in (a) and (c) are both lattices because
in each poset every pair of elements has both a least upper bound and a greatest lower bound,
as the reader should verify. On the other hand, the poset with the Hasse diagram shown in (b)
is not a lattice, because the elements b and c have no least upper bound. To see this, note that
each of the elements d, e, and f is an upper bound, but none of these three elements precedes
the other two with respect to the ordering of this poset. ▲

f f h

e d e e g g
c d

b b c b d d

a a a
(a) (b) (c)

FIGURE 8 Hasse Diagrams of Three Posets.