354 ORDERED SETS AND LATTICES [CHAP. 14
Fig. 14-11
14.11. Repeat Problem 14.10 for the subsetB={ 1 , 2 , 5 }.
(a) There is no upper bound forBsince no element succeeds both 1 and 2. The lower bounds are 6, 7, 8.
(b) Trivially, sup(A)does not exist since there are no upper bounds. AlthoughAhas three lower bounds, inf(A)
does not exist since no lower bound succeeds both 6 and 7.14.12. Consider the setQof rational numbers with the usual order≤. Consider the subsetDofQdefined by
D={x|x∈Qand 8<x^3 < 15 }(a)IsDbounded above or below? (b) Does sup(D)or inf(D)exist?
(a) The subsetDis bounded both above and below. For example, 1 is a lower bound and 100 an upper bound.
(b) We claim that sup(D)does not exist. Suppose, on the contrary, sup(D)=x. Since^3√
15 is irrational,x>^3√
15.
However, there exists a rational numberysuch that^3√
15 <y<x. Thusyis also an upper bound forD. This
contradicts the assumption thatx=sup(D). On the other hand, inf(D)does exist. Specifically, inf(D)=2.ISOMORPHIC (SIMILAR) SETS, SIMILARITY MAPPINGS
14.13. Suppose a poset A is isomorphic (similar) to a posetBandf:A→Bis a similarity mapping. Are the
following statements true or false?(a) An elementa∈Ais a first (last, minimal, or maximal) element ofAif and only iff(a)is a first (last,
minimal, or maximal) element ofB.
(b) Anelementa∈Aimmediatelyprecedesanelementa′∈A,thatis,a/a′,ifandonlyiff(a)/f(a′).
(c) An elementa∈Ahasrimmediate successors inAif and only iff(a)hasrimmediate successors inB.All the statements are true; the order structure ofAis the same as the order structure ofB.14.14. LetS={a, b, c, d, e}be the ordered set in Fig. 14-12(a). SupposeA={ 1 , 2 , 3 , 4 , 5 }is isomorphic to
S. Draw the Hasse diagram ofAif the following is a similarity mapping fromStoA:
f={(a, 1 ), (b, 3 ), (c, 5 ), (d, 2 ), (e, 4 )}The similarity mapping f preserves the order structure ofSand hencefmay be viewed simply as a relabeling
of the vertices in the diagram ofS. Thus Fig. 14-12(b)shows the Hasse diagram ofA.
14.15. LetA={ 1 , 2 , 3 , 4 , 5 }is ordered as in Fig. 14-12(b). Find the numbernof similarity mappingsf:A→A.
Since 1 is the only minimal element ofAand 4 is the only maximal element, we must havef( 1 )=1 and
f( 4 )=4. Also,f( 3 )=3 since 3 is the only immediate successor of 1. On the other hand, there are two possibilities
forf( 2 )andf( 5 ), that is, we can havef( 2 )=2 andf( 5 )=5, orf( 2 )=5 andf( 5 )=2. Accordingly,n=2.14.16. Give an example of a finite nonlinearly ordered setX=(A, R)which is isomorphic toY=(A, R−^1 ),
the setAwith the inverse order.
LetRbe the partial ordering ofA={a, b, c, d, e}pictured in Fig. 14-13(a).
Then Fig. 14-13(b)showsAwith the inverse orderR. (The diagram ofRis simply turned upside down to obtain
R−^1 .) Notice that the two diagrams are identical except for the labeling. ThusXis isomorphic toY.