Discrete Mathematics for Computer Science

Ordering Relations 197

Definition 4. Let R be a partial ordering or a linear ordering on a set X. For x, y e X, if

x R y and x 0 y, then x is below y. We say x is above y if y is below x.

Example 11. Let X = {1, 2, 3, 41 be a set. P(X) together with C is a partial order. {I}

is below {1, 2}. {1, 21 is below {1, 2, 3, 41. {2, 31 is above both {2} and {3}. {1, 2, 3, 41 is
above each element of P(X) distinct from itself.

Observe that the relations "above" and "below" are transitive.

Definition 5. Let R be a partial or a linear ordering on a set X. Let x e X.

(a) x is a minimal element of X if there is no y E X such that y is below x.
(b) x is the minimum element of X if x is below every other element of X.
(c) x is a maximal element of X if there is no y e X such that y is above x.
(d) x is the maximum element of X if x is above every other element of X.

In contexts where it is not clear what ordering is being discussed, write R-minimal,
R-minimum, R-maximal, and R-maximum to clarify that the ordering relation is R.
Consider the ordering shown in Figure 3.16. In this ordering, A is the maximum ele-
ment and the only maximal element. D, E, and F are all minimal elements. There is no
minimum element.

A

B C

D E \F

Figure 3.16 A partial ordering P.

Turning the order in Figure 3.16 upside down produces the order shown in Figure
3.17. In this ordering, A is the minimum element, and D, E, and F are maximal elements.
There is no maximum element.

D E F

B \ C

A

Figure 3.17 Partial ordering P upside down.

Theorem 2. Let R be a partial ordering on X, and let x, y e X.

(a) If both x and y are minimum elements, then x = y. This justifies speaking of the
minimum element.
(b) If x is the minimum element of X, then x is the unique minimum element of X.
(c) If R is a linear ordering on X, then x is minimal if and only if x is the minimum
element.
(d) An element x E X is R-minimal if and only if x is R-^1 -maximal, and x is the
R-minimum element if and only if x is the R-'-maximum element.
(e) The analogous results to parts (a) through (d) are true, with minimum replaced with
maximum and minimal with maximal.