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

CHAP. 14] ORDERED SETS AND LATTICES 343

EXAMPLE 14.6

(a) LetS={a, b, c, d, e, f}be ordered as pictured in Fig. 14-3(a), and letA={b, c, d}. The upper bounds of

Aareeandfsince onlyeandfsucceed every element inA. The lower bounds ofAareaandbsince only

aandbprecede every element ofA. Note thateandf are noncomparable; hence sup(A)does not exist.

However,balso succeedsa, hence inf(A)=b.

(b) LetS={ 1 , 2 , 3 ,..., 8 }be ordered as pictured in Fig. 14-3(b), and letA={ 4 , 5 , 7 }. The upper bounds of

Aare 1, 2, and 3, and the only lower bound is 8. Note that 7 is not a lower bound since 7 does not precede 4.

Here sup(A)=3 since 3 precedes the other upper bounds 1 and 2. Note that inf(A)=8 since 8 is the only

lower bound.

Fig. 14-3 Fig. 14-4

Generally speaking, sup(a, b)and inf(a, b)need not exist for every pair of elementsaandbin a posetS.
We now give two examples of partially ordered sets where sup(a, b)and inf(a, b)do exist for everya,bin
the set.

EXAMPLE 14.7

(a) Let the setNof positive integers be ordered by divisibility. Thegreatest common divisorofaandbinN,

denoted by

gcd(a, b)

is the largest integer which dividesaandb. Theleast common multipleofaandb, denoted by

lcm(a, b)

is the smallest integer divisible by bothaandb.

An important theorem in number theory says that every common divisor ofaandbdivides gcd(a, b).

One can also prove that lcm(a, b)divides every multiple ofaandb. Thus

gcd(a, b)=inf(a, b) and lcm(a, b)=sup(a, b)

In other words, inf(a, b)and sup(a, b)do exist for any pair of elements ofNordered by divisibility.

(b) For any positive integerm, we will letDmdenote the set of divisors ofmordered by divisibility. The Hasse

diagram of

D 36 ={ 1 , 2 , 3 , 4 , 6 , 9 , 12 , 18 , 36 }

appears in Fig. 14-4. Again, inf(a, b)=gcd(a, b)and sup(a, b)=lcm(a, b)exist for any paira,binDm.