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

CHAP. 14] ORDERED SETS AND LATTICES 355

Fig. 14-12

Fig. 14-13

14.17. LetAbe an ordered set and, for eacha∈A, letp(a)denote the set of predecessors ofa:

p(a)={x|x
a}

(called thepredecessor setofa). Letp(A)denote the collection of all predecessor sets of the elements

inAordered by set inclusion.

(a) Show thatAandp(A)are isomorphic by showing that the mapf:A→p(A), defined byf(a)=p(a),

is a similarity mapping ofAontop(A).

(b) Find the Hasse diagram ofp(A)for the setAin Fig. 14-13(a).

(a) First we show thatfpreserves the order relation ofA. Supposea
b. Letx∈p(a). Thenx
a, and hence

a
b;sox∈p(b). Thusp(a)⊆p(b). Supposea‖b(noncomparable). Thena∈p(a)buta/∈p(b); hence

p(a)⊆p(b). Similarly,b∈p(b)butb/∈p(a); hencep(b)⊆p(a). Therefore,p(a)‖p(b). Thusfpreserves

order.

We now need only show thatfis one-to-one and onto. Supposey∈p(A). Theny=p(a)for somea∈A.

Thusf(a)=p(a)=ysofis ontop(A). Supposea=b. Thena≺b,b≺aora‖b. In the first and third

cases,b∈p(b)butb/∈p(a), and in the second casea∈p(a)buta/∈p(b). Accordingly, in all three cases, we

havep(a)=p(b). Thereforefis one-to-one.

Consequently,fis a similarity mapping ofAontop(A)and soAp(A).

(b) The elements ofp(A)follow:

p(a)={a, c, d, e}, p(b)={b, c, d, e}, p(c)={c, d, e}, p(d)={d}, p(e)={e}

Figure 14-13(c) gives the diagram ofp(A)ordered by set inclusion. Observe that the diagrams in Fig. 14-13(a)

and (c) are identical except for the labeling of the vertices.

WELL-ORDERED SETS

14.18. Prove the Principle of Transfinite Induction: LetAbe a subset of a well-ordered setSwith the following
two properties: (i)a 0 ∈A. (ii) Ifs(a)⊆Athena∈A. ThenA=S.
(Herea 0 is the first element ofA, ands(a)is the initial segment of a, i.e., the set of all elements strictly precedinga.)
SupposeA=S. LetB=S\A.ThenB=
. SinceSis well-ordered, B has a first elementb 0. Each elementx∈s(b 0 )