Discrete Mathematics for Computer Science

198 CHAPTER^3 Relations

Proof. Proofs of (a) through (e) are left as exercises for the reader. U

For infinite sets like Z, there is no minimum, maximum, minimal, or maximal element.

Every finite partially ordered set has at least one minimal element and at least one maximal

element. Every finite linearly ordered set has exactly one minimum element and exactly

one maximum element. This result (for minimal elements and minimums) is proved in

Theorem 3.

Theorem 3. Let R be a partial ordering on afinite set X, and let x E X.

(a) Either x is minimal or there is a minimal element y E X below x.

(b) If x is the only minimal element of X, then x is the minimum element.

(c) If R is a linear ordering, then there is a minimum element in X.

Proof (a) Let z 1 E X. If z 1 is not minimal, there is some Z2 E X that is below z 1. If Z2 is

not minimal, we can find a Z3 below Z2. Continue in this fashion. (See Figure 3.18.) Since

X has only finitely many elements, the process must terminate after, at most, JXJ steps,

finding an element Zk for which k < I X I and for which there is no element of X below Zk.

Then, zk is a minimal element below Zl.

Zl

Figure 3.18 Elements below x and z.

(b) minimal Let z0 e element X be the only minimal element, and let z e X. By part (a), there is some

below z. That minimal element must be z0 itself, because zo is

the

only minimal element. So, zo is the minimum element.

(c) By minimum part (a), element. there is a minimal element of X. By Theorem 2(c), that element is the

e

Of course, exactly analogous results hold for maximal and maximum

sets. elements in finite

The reader should construct examples to show that results these

do not necessarily

hold if the set is infinite.

3.8.5 Application: Finding a Minimal Element

The proof of Theorem 3(a) suggests an algorithm that can be

used for finding a minimal

element of a finite set where R is a partial or linear ordering.