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

358 ORDERED SETS AND LATTICES [CHAP. 14

Fig. 14-15

(c) Which of the following are sublattices ofL:

L 1 ={ 0 ,a,b,I},L 2 ={ 0 ,a,e,I},L 3 ={a, c, d, I},L 4 ={ 0 ,c,d,I}

(d)IsLdistributive?

(e) Find complements, if they exist, for the elements,a,bandc.

(f)IsLa complemented lattice?

(a) Those nonzero elements with a unique immediate predecessor are join irreducible. Hencea,b,d, andeare join

irreducible.

(b) Those elements which immediately succeed 0 are atoms, henceaandbare the atoms.

(c) A subsetL′is a sublattice if it is closed under∧and∨.L 1 is not a sublattice sincea∨b=c, which does not

belong toL 1. The setL 4 is not a sublattice sincec∧d=adoes not belong toL 4. The other two sets,L 2 and

L 3 , are sublattices.

(d) Lis not distributive sinceM={ 0 ,a,d,e,I}is a sublattice which is isomorphic to the nondistributive lattice in

Fig. 14-7(a).

(e) We havea∧e=0 anda∨e=I,soaandeare complements. Similarly,banddare complements. However,

chas no complement.

(f) Lis not a complemented lattice sincechas no complement.

14.27. Consider the latticeMin Fig. 14-15(b).

(a) Find the nonzero join irreducible elements and atoms ofM.

(b)IsM(i) distributive? (ii) complemented?

(a) The nonzero elements with a unique predecessor area,b, andd, and of these three onlyaandbare atoms since

their unique predecessor is 0.

(b) (i)Mis distributive sinceMdoes not have a sublattice isomorphic to one of the lattices in Fig. 14-7. (ii)Mis

not complemented sincebhas no complement. Noteais the only solution tob∧x=0 butb∧a=c=I.

14.28. Prove Theorem 14.8: LetLbe a finite distributive lattice. Then everya∈Lcan be written uniquely
(except for order) as the join of irredundant join irreducible elements.
SinceLis finite we can writeaas the join of irredundant join irreducible elements as we discussed in Section 14.9.
Thus we need to prove uniqueness. Suppose

a=b 1 ∨b 2 ∨···∨br=c 1 ∨c 2 ∨···∨cs

where theb’s are irredundant and join irreducible and thec’s are irredundant and irreducible. For any giveniwe have

bi
(b 1 ∨b 2 ∨···∨br)=(c 1 ∨c 2 ∨···∨cs)