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

350 ORDERED SETS AND LATTICES [CHAP. 14

If an elementain a finite latticeLis not join irreducible, then we can writea=b 1 ∨b 2. Then we can write
b 1 andb 2 as the join of other elements if they are not join irreducible; and so on. SinceLis finite we finally have

a=d 1 ∨d 2 ∨···∨dn

where thed’s are join irreducible. Ifdiprecedesdjthendi∨dj=dj; so we can delete thedifrom the expression.
In other words, we can assume that thed’s areirredundant, i.e., nodprecedes any otherd. We emphasize that
such an expression need not be unique, e.g.,I=a∨bandI=b∨cin both lattices in Fig. 14-7. We now state
the main theorem of this section (proved in Problem 14.28.)

Theorem 14.8: LetLbe a finite distributive lattice. Then everyainLcan be written uniquely (except for order)
as the join of irredundant join irreducible elements.
Actually this theorem can be generalized to lattices withfinite length, i.e., where all linearly ordered subsets
are finite. (Problem 14.30 gives an infinite lattice with finite length.)

14.11Complements, Complemented Lattices

LetLbe a bounded lattice with lower bound 0 and upper boundI. Letabe an element ofL. An elementx
inLis called acomplementofaif
a∨x=I and a∧x= 0

Complements need not exist and need not be unique. For example, the elementsaandcare both complements
ofbin Fig. 14-7(a). Also, the elementsy,z,anduin the chain in Fig. 14-1 have no complements. We have the
following result.

Theorem 14.9: LetLbe a bounded distributive lattice. Then complements are unique if they exist.

Proof:Supposexandyare complements of any elementainL. Then

a∨x=I, a∨y=I, a∧x= 0 ,a∧y= 0

Using distributivity,

x=x∨ 0 =x∨(a∧y)=(x∨a)∧(x∨y)=I∧(x∨y)=x∨y

Similarly,
y=y∨ 0 =y∨(a∧x)=(y∨a)∧(y∨x)=I∧(y∨x)=y∨x

Thus
x=x∨y=y∨x=y

and the theorem is proved.

Complemented Lattices

AlatticeLissaidtobecomplementedifLisboundedandeveryelementinLhasacomplement.Figure14-7(b)
shows a complemented lattice where complements are not unique. On the other hand, the latticeP(U)of all subsets
of a universal setUiscomplemented,and each subsetAofUhas the unique complementAc=U\A.

Theorem 14.10: LetLbe a complemented lattice with unique complements. Then the join irreducible elements
ofL, other than 0, are its atoms.
Combining this theorem and Theorems 14.8 and 14.9, we get an important result.

Theorem 14.11: LetLbe a finite complemented distributive lattice. Then every elementainLis the join of a
unique set of atoms.

Remark: SometextsdefinealatticeLtobecomplementedifeachainLhasauniquecomplement.Theorem14.10
is then stated differently.