Discrete Mathematics for Computer Science

194 CHAPTER 3 Relations

Solution. We must show that R is reflexive, antisymmetric, and transitive.

Reflexive: Let U, V C X. If U = V, then (U, V) e R by definition of R.

Antisymmetric: Let (U, V) E R, and suppose U # V. Then, I U I < I V 1, so I V I 7I U I.

Thus, (V, U) € R.

Transitive: Let U, V, W C X. Let (U, V) E R and (V, W) E R. Show that (U, W) e R.

There are four cases, depending on why (U, V) e R and why (V, W) e R.

Case: U = V, andV= W. Then, U = W, soURW.

Case 2: U = V, and I V I < IW .Then, I U I = I V I < I W I, so (U, W) E R.

Case 3: 1 U < I V [, and V = W. This proof is analogous to the proof for Case 2.

Case 4: 1 U I < V I, and I V< I W I. Since < is a transitive relation on N, I U I < [ W I.

Hence, (U, W) e R.

Since R is reflexive, antisymmetric, and transitive, R is a partial order. U

3.8.2 Linear Orderings

The relation less than (<) on the integers has the property that for any n and m with m A n,

either n < m or m < n. This property is not true for the relation of set inclusion (S). The

set X = {0, 1,2, 3} has subsets x = {0, 2) and y = {0, 1, 3) for which neither is a subset

of the other. Relations other than ones defined on a number system sometimes, however,

satisfy this property, which makes it an important property of ordering relations.

Definition 2. Let R be a binary relation on a set X. R is a linear ordering, or total

ordering, on X if R is a transitive relation that satisfies the law of trichotomy: For every

x, y E X, exactly one of the following conditions holds: (i) x R y, (ii) x = y, or (iii) y R x.

Example 8. The following are linear orderings:

(a) < is a linear ordering on R. The name linear ordering suggests points on a line, and

R is the standard mathematical model of a line. Condition (ii) is never true for this

relation!

(b) < is a linear ordering on N.

(c) Let M be the set of kings and queens of England since 1850. For X, Y E M, set X R Y

if X ruled before Y. Then, R is a linear ordering on M.

The relation < on IR is not a linear ordering, because for any x E IR, both x = x and

x < x hold. The law of trichotomy requires that exactly one of the three properties hold.

Example 9. (Lexicographical or Dictionary Ordering) The alphabetical (dictionary)

ordering of words is the basis for being able to sort sets of words in increasing or decreasing

order. For example, let English be the set of words in the latest edition of the Oxford English

Dictionary, and let < be their alphabetical ordering, in which the letters of the alphabet are

ordered from a to z, with blank being less than a. For this example, we will assume that

all words in the dictionary begin with lowercase letters. (With computers, lowercase and

uppercase letters have different representations.) Describe how two words are compared

using this ordering.