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) Let z0 e X be the only minimal element, and let z e X. By part (a), there is some
minimal element below z. That minimal element must be z0 itself, because zo is the
only minimal element. So, zo is the minimum element.
(c) By part (a), there is a minimal element of X. By Theorem 2(c), that element is the
minimum element.
e
Of course, exactly analogous results hold for maximal and maximum elements in finite
sets. The reader should construct examples to show that
these
results 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.
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) Let z0 e X be the only minimal element, and let z e X. By part (a), there is some
minimal element below z. That minimal element must be z0 itself, because zo is the
only minimal element. So, zo is the minimum element.
(c) By part (a), there is a minimal element of X. By Theorem 2(c), that element is the
minimum element.
e
Of course, exactly analogous results hold for maximal and maximum elements in finite
sets. The reader should construct examples to show that
these
results 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.