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

CHAP. 14] ORDERED SETS AND LATTICES 341

EXAMPLE 14.4 Apartitionof a positive integermis a set of positive integers whose sum ism. For instance,
there are seven partitions ofm=5 as follows:

5 , 3 − 2 , 2 − 2 − 1 , 1 − 1 − 1 − 1 − 1 , 4 − 1 , 3 − 1 − 1 , 2 − 1 − 1 − 1

We order the partitions of an integermas follows. A partitionP 1 precedes a partitionP 2 if the integers inP 1 can
be added to obtain the integers inP 2 or, equivalently, if the integers inP 2 can be further subdivided to obtain the
integers inP 1. For example,
2 − 2 −1 precedes 3− 2

since 2+ 1 =3. On the other hand, 3− 1 −1 and 2− 2 −1 are noncomparable.
Figure 14-2 gives the Hasse diagram of the partitions ofm=5.

Fig. 14-2

Minimal and Maximal, and First and Last Elements

LetSbe a partially ordered set.An elementainSis called aminimalelement if no other element ofSstrictly
precedes (is less than)a. Similarly, an elementbinSis called amaximalelement if no element ofSstrictly
succeeds (is larger than)b. Geometrically speaking,ais a minimal element if no edge entersa(from below),
andbis a maximal element if no edge leavesb(in the upward direction). We note thatScan have more than one
minimal and more than one maximal element.
IfSis infinite, thenSmay have no minimal and no maximal element. For instance, the setZof integers with
the usual order≤has no minimal and no maximal element. On the other hand, ifSis finite, thenSmust have at
least one minimal element and at least one maximal element.
An elementaisSis called afirstelement if for every elementxinS,
a
x

that is, ifaprecedes every other element inS. Similarly, an elementbinSis called alastelement if for every
elementyinS,
y
b

that is, ifbsucceeds every other element inS. We note thatScan have at most one first element, which must
be a minimal element, andScan have at most one last element, which must be a maximal element. Generally
speaking,Smay have neither a first nor a last element, even whenSis finite.

EXAMPLE14.5

(a) Consider the three partially ordered sets in Example 14-3 whose Hasse diagrams appear in Fig. 14-1.

(i) Ahas two maximal elements 18 and 24 and neither is a last element.Ahas only one minimal element, 1,

which is also a first element.

(ii) Bhas two minimal elements,dande, and neither is a first element.Bhas only one maximal element,a,

which is also a last element.

(iii) The chain has one minimal element,x, which is a first element, and one maximal element,v, which is

a last element.