Discrete Mathematics for Computer Science

196 CHAPTER 3 Relations

3.8.3 Comparable Elements

Definition 3. Let R be a partial or linear ordering on a set X. Elements x, y E X are said

to be comparable under R if x R y or y R x (or both) holds.

Example 10. For X = {0, 1, 2, 31 partially ordered by the relation set inclusion P(X),

then, {0, 1) and {0, 1, 21 are comparable, but 10, 2, 31 and {0, 1) are not.

Observe that if R is a linear ordering on a set X with x, y e X and x A y, then x and

y are comparable by the law of trichotomy. Observe also that if R and S are linear or partial

orders such that R C S, then if x and y are comparable in R, they are also comparable in S.

Theorem 1.

(a) If R is a linear ordering of a set X, then R U ldx is a partial ordering of X.

(b) If R is a partial ordering of X, then R - IdX is a linear ordering of X if and only if,

for any x, y E X, the elements x and y are comparable under R.

Proof. (a) This proof is left as an exercise for the reader.

(b) (=•) First, suppose R - Idx is a linear ordering. Let x, y • X. It is necessary to show

that x and y are comparable under R. If x 0 y, then x and y are comparable in R - Idx

and, hence, in R by the observation before the theorem. If x = y, then (x, y) = (x, x) E R,

because Idx C R.

(.=) Let x, y E X. Note that since R is antisymmetric,

(x, y) E R - Idx =_ (y, x) 0 R

Transitive: Let (x, y), (y, z) E R - IdX. Then, (x, z) E R, because R is transitive. Fur-

thermore, x : z since (y, z) E R, whereas since R is antisymmetric, (y, x) 0 R. There-

fore, (x, z) E R - Idx.

Trichotomy: We must show exactly one of (i) (x, y) E R - Idx, (ii) x = y, or (iii)

(y, x) E R - Idx holds. We see that at most one of these can hold from the antisymmetric

property of R and the obvious fact that

(R - Idx) n ldx = 0

To see that at least one of these holds, let x, y E X with x : y. Since x and y are compa-

rable under R, we have (x, y) e R or (y, x) E R. Since x - y, either (x, y) E R - Idx or

(y, x) E R- Idx.

Theorem I shows that there are two differences between partial and linear orderings:

1. Partial orderings are reflexive, whereas linear orderings are irreflexive.


2. Any two unequal elements of a linearly ordered set are comparable. This need not be
   true with partial orderings.

3.8.4 Optimal Elements in Orderings

The next property to investigate in an ordering relation is whether an ordering contains an

element that is optimal in the sense that it is "larger" or "smaller" than any element to

which it is comparable. This element may not be unique; for example, {{1}, (1, 3}, 1211

under the relation C has both 11, 31 and {2) as "larger" than any element(s) to which they

are comparable. The properties of interest are more formally defined here.