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

342 ORDERED SETS AND LATTICES [CHAP. 14

(b) LetAbe any nonempty set and letP (A)be the power set ofAordered by set inclusion. Then the empty set


is a first element ofP (A)since, for any setX, we have
⊆X. Moreover,Ais a last element ofP (A)

since every elementYofP (A)is, by definition, a subset ofA, that is,Y⊆A.

14.4Consistent Enumeration

SupposeSis a finite partially ordered set. Frequently we want to assign positive integers to the elements ofS
in such a way that the order is preserved. That is, we seek a functionf:S→Nso that ifa≺bthenf(a)<f(b).
Such a function is called aconsistent enumerationofS. The fact that this can always be done is the content of
the following theorem.

Theorem 14.1: There exists a consistent enumeration for any finite posetA.

We prove this theorem in Problem 14.8. In fact, we prove that ifShasnelements then there exists a consistent
enumerationf:S→{ 1 , 2 ,...,n}.
We emphasize that such an enumeration need not be unique. For example, the following are two such
enumerations for the poset in Fig. 14-1(b):

(i) f(d)=1,f(e)=2,f(b)=3,f(c)=4,f(a)=5.

(ii) g(e)=1,g(d)=2,g(c)=3,g(b)=4,g(a)=5.

However the chain in Fig. 14-1(c)admits only one consistent enumeration if we map the set into{ 1 , 2 , 3 , 4 , 5 }.
Specifically, we must assign:

h(x)= 1 , h(y)= 2 , h(z)= 3 , h(u)= 4 , h(v)= 5

14.5Supremum and Infimum

LetAbe a subset of a partially ordered setS.An elementMinSis called anupper boundofAifMsucceeds

every element ofA, i.e., if, for everyxinA, we have

x
M

If an upper bound ofAprecedes every other upper bound ofA, then it is called thesupremumofAand is
denoted by

sup(A)

We also write sup(a 1 ,...,an)instead of sup(A)ifAconsists of the elementsa 1 ,...,an. We emphasize that
there can be at most one sup(A); however, sup(A)may not exist.
Analogously, an elementmin a posetSis called alower boundof a subsetAofSifmprecedes every
element ofA, i.e., if, for everyyinA, we have

m
y

If a lower bound ofAsucceeds every other lower bound ofA, then it is called theinfimumofAand is denoted by

inf(A), or inf(a 1 ,...,an)

ifAconsists of the elementsa 1 ,...,an. There can be at most one inf(A)although inf(A)may not exist.

Some texts use the termleast upper boundinstead of supremum and then write lub(A)instead of sup(A),
and use the termgreatest lower boundinstead of infimum and write glb(A)instead of inf(A).
IfAhas an upper bound we sayAisbounded above, and ifAhas a lower bound we sayAisbounded below.
In particular,AisboundedifAhas an upper and lower bound.