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

CHAP. 14] ORDERED SETS AND LATTICES 349

14.10Distributive Lattices

A latticeLis said to bedistributiveif for any elementsa,b,cinLwe have the following:

[L 4 ] Distributive law:

( 4 a) a∧(b∨c)=(a∧b)∨(a∧c) ( 4 b) a∨(b∧c)=(a∨b)∧(a∨c)

Otherwise,Lis said to benondistributive. We note that by the principle of duality the condition (4a) holds if and
only if (4b) holds.
Figure 14-7(a)is a nondistributive lattice since

a∨(b∧c)=a∨ 0 =a but (a∨b)∧(a∨c)=I∧c=c

Figure 14-7(b)is also a nondistributive lattice. In fact, we have the following characterization of such lattices.

Fig. 14-7

Theorem 14.7:A latticeLis nondistributive if and only if it contains a sublattice isomorphic to Fig. 14-7(a)or
to Fig. 14.7(b).
The proof of this theorem lies beyond the scope of this text.

Join Irreducible Elements, Atoms

LetLbe a lattice with a lower bound 0. An elementainLis said to bejoin irreducibleifa=x∨yimplies
a=xora=y. (Prime numbers under multiplication have this property, i.e., ifp=abthenp=aorp=b
wherepis prime.) Clearly 0 is join irreducible. Ifahas at least two immediate predecessors, say,b 1 andb 2 as in
Fig. 14-8(a), thena=b 1 ∨b 2 , and soais not join irreducible. On the other hand, ifahas a unique immediate
predecessorc, thena=sup(b 1 ,b 2 )=b 1 ∨b 2 for any other elementsb 1 andb 2 becausecwould lie between the
b’s andaas in Fig. 14-8(b). In other words,a=0, is join irreducible if and only ifahas a unique immediate
predecessor. Those elements which immediately succeed 0, calledatoms, are join irreducible. However, lattices
can have other join irreducible elements. For example, the elementcin Fig. 14-7(a)is not an atom but is join
irreducible sinceais its only immediate predecessor.

Fig. 14-8