344 ORDERED SETS AND LATTICES [CHAP. 14
14.6Isomorphic (Similar) Ordered Sets
SupposeXandYare partially ordered sets.Aone-to-one (injective) functionf:X→Yis called asimilarity
mappingfromXintoYiffpreserves the order relation, that is, if the following two conditions hold for any pair
aanda′inX:
(1) Ifaa′thenf(a)f(a′).(2) Ifa‖a′(noncomparable), thenf(a)‖f(a′).Accordingly, ifAandBare linearly ordered, then only (1) is needed forfto be a similarity mapping.
Two ordered setsXandYare said to beisomorphicorsimilar, written
X Yif there exists a one-to-one correspondence (bijective mapping)f:X→Ywhich preserves the order relations,
i.e., which is a similarity mapping.
EXAMPLE 14.8 SupposeX={ 1 , 2 , 6 , 8 , 12 }is ordered by divisibility and supposeY={a, b, c, d, e}is
isomorphic toX; say, the following functionfis a similarity mapping fromXontoY:
f={( 1 , e), ( 2 , d), ( 6 , b), ( 8 , c), ( 12 ,a)}Draw the Hasse diagram ofY.
The similarity mapping preserves the order of the initial setXand is one-to-one and onto. Thus the mapping
can be viewed simply as a relabeling of the vertices in the Hasse diagram of the initial setX. The Hasse diagrams
for bothXandYappear in Fig. 14-5.
Fig. 14-514.7Well-Ordered Sets
We begin with a definition.Definition 14.1: An ordered setSis said to bewell-orderedif every subset ofShas a first element.
The classical example of a well-ordered set is the setNof positive integers with the usual order≤.
The following facts follow from the definition.
(1) A well-ordered set is linearly ordered. For ifa,b,∈S, then{a, b}has a first element; henceaandbare
comparable.
(2) Every subset of a well-ordered set is well-ordered.
(3) IfXis well-ordered andYis isomorphic toX, thenYis well-ordered.
(4) All finite linearly ordered sets with the same numbernof elements are well-ordered and are all isomorphic
to each other. In fact, they are all isomorphic to{ 1 , 2 ,...,n}with the usual order≤.