Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

348 ORDERED SETS AND LATTICES [CHAP. 14

Theorem 14.5: LetPbe a poset such that the inf(a, b)and sup(a, b)exist for anya,binP. Letting

a∧b=inf(a, b) and a∨b=sup(a, b)

we have that(P ,∧,∨)is a lattice. Furthermore, the partial order onPinduced by the lattice is
the same as the original partial order onP.
The converse of the above theorem is also true. That is, letLbe a lattice and let
be the induced partial order
onL. Then inf(a, b)and sup(a, b)exist for any paira,binLand the lattice obtained from the poset(L,
)is
the original lattice. Accordingly, we have the following:

Alternate Definition: A lattice is a partially ordered set in which

a∧b=inf(a, b) and a∨b=sup(a, b)

exist for any pair of elementsaandb.
We note first that any linearly ordered set is a lattice since inf(a, b)=aand sup(a, b)=bwhenever
a
b. By Example 14.7, the positive integersNand the setDmof divisors ofmare lattices under the relation of
divisibility.

Sublattices, Isomorphic Lattices

SupposeMis a nonempty subset of a latticeL. We sayMisa sublatticeofLifMitself is a lattice (with
respect to the operations ofL). We note thatMis a sublattice ofLif and only ifMis closed under the operations of
∧and∨ofL. For example, the setDmof divisors ofmis a sublattice of the positive integersNunder divisibility.
Two latticesLandL′are said to beisomorphicif there is a one-to-one correspondencef:L→L′such that

f(a∧b)=f(a)∧f(b) and f(a∨b)=f(a)∨f(b)

for any elementsa,binL.

14.9Bounded Lattices

A latticeLis said to have alower bound0 if for any elementxinLwe have 0
x. Analogously,Lis said
to have anupper bound Iif for anyxinLwe havex
I. We sayLisboundedifLhas both a lower bound 0
and an upper boundI. In such a lattice we have the identities

a∨I=I, a∧I=a, a∨ 0 =a, a∧ 0 = 0

for any elementainL.
The nonnegative integers with the usual ordering,

0 < 1 < 2 < 3 < 4 <···

have 0 as a lower bound but have no upper bound. On the other hand, the latticeP(U)of all subsets of any
universal setUis a bounded lattice withUas an upper bound and the empty set
as a lower bound.
SupposeL={a 1 ,a 2 ,...,an}is a finite lattice. Then

a 1 ∨a 2 ∨···∨an and a 1 ∧a 2 ∧···∧an

are upper and lower bounds forL, respectively. Thus we have

Theorem 14.6: Every finite latticeLis bounded.