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

CHAP. 14] ORDERED SETS AND LATTICES 357

14.22. LetAbe a well-ordered set. Lets(A)denote the collection of all initial segmentss(a)of elementsa∈A
ordered by set inclusion. ProveAis isomorphic tos(A)by showing that the mapf:A→s(A), defined
byf(a)=s(a), is a similarity mapping ofAontos(A). (Compare with Problem 14.17.)
First we show thatfis one-to-one and onto. Supposey ∈s(A). Theny =s(a)for somea ∈A. Thus
f(a)=s(a)=y,sofis ontos(A). Supposex=y. Then one precedes the other, say,x≺y. Thenx∈s(y). But
x/∈s(x). Thuss(x)=s(y). Therefore,fis also one-to-one.
We now need only show thatfpreserves order, that is,

x
y if and only if s(x)⊆s(y)

Supposex
y.Ifa∈s(x), thena≺xand hencea≺y; thusa∈s(y). Thuss(x)⊆s(y). On the other hand,

supposex
y, that is,x.y. Theny∈s(x). Buty/∈s(y); hences(x)⊆s(y). In other words,x
yif and only if

s(x)⊆s(y). Accordingly,fis a similarity mapping ofAontoS(A), and soA∼=s(A).

LATTICES

14.23. Write the dual of each statement:

(a) (a∧b)∨c=(b∨c)∧(c∨a); (b) (a∧b)∨a=a∧(b∨a).

Replace∨by∧and replace∧by∨in each statement to obtain the dual statement:

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

14.24. Prove Theorem 14.4: Let L be a lattice. Then:

(i) a∧b=aif and only ifa∨b=b.

(ii) The relationa
b(defined bya∧b=aora∨b=b) is a partial order onL.

(i) Supposea∧b=a. Using the absorption law in the first step we have:

b=b∨(b∧a)=b∨(a∧b)=b∨a=a∨b

Now supposea∨b=b. Again using the absorption law in the first step we have:

a=a∧(a∨b)=a∧b

Thusa∧b=aif and only ifa∨b=b.

(ii) For anyainL, we havea∧a=aby idempotency. Hencea
a, and so
is reflexive.

Supposea
bandb
a. Thena∧b=aandb∧a=b. Therefore,a=a∧b=b∧a=b, and so
is

antisymmetric.

Lastly, supposea
bandb
c. Thena∧b=aandb∧c=b. Thus

a∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a

Thereforea
c, and so
is transitive. Accordingly,
is a partial order onL.

14.25. Which of the partially ordered sets in Fig. 14-15 are lattices?

A partially ordered set is a lattice if and only if sup(x, y)and inf(x, y)exist for each pairx,yin the set. Only

(c) is not a lattice since{a, b}has three upper bounds,c,dandI, and no one of them precedes the other two, that is,

sup(a, b)does not exist.

14.26. Consider the latticeLin Fig. 14-15(a).

(a) Which nonzero elements are join irreducible?

(b) Which elements are atoms?