Discrete Mathematics for Computer Science

Special Types of Relations 171

Definition 4. Let R be a binary relation on a set X. R is antisymmetric if (y, x) 0 R

whenever (x, y) c R and x 0 y.

The relation defined on 1, 2, 31 as R = {(1, 2), (2, 1), (3, 2)} is neither symmetric,

because (3, 2) E R but (2, 3) 0 R, nor antisymmetric, because both (1, 2) and (2, 1) are

in R.

The relations =, <, and < are all antisymmetric. A logically equivalent statement of

the definition of antisymmetric is the following: If (x, y) and (y, x) are both in R, then

y = x. To see this in terms of the logical notation introduced in Chapter 2, let p1 be the

statement "(x, y) E R,"p 2 the statement "(y, x) E R," and P3 the statement "x = y." The

definition is of the form (pl A -P3) -+ -•P2, which is logically equivalent to the formula

(P1 A P2) -- P3.

Example 3. See Section 3.1 for the examples and the definitions of the relations IsPar-

entOf and HigherValue.

(a) In the family tree example, the relation IsParentOf is antisymmetric. For example,

(Mary, Elaine) E IsParentOf but (Elaine, Mary) 0 IsParentOf.

(b) In the card example, HigherValue is antisymmetric. We see this as (Jack of Hearts, 10

of Hearts) E HigherValue, but (10 of Hearts, Jack of Hearts) g HigherValue.

Suppose that a binary relation R is written as a table T, as in Table 3.7(a), which

repeats the information contained in Table 3.4. Now, suppose that a new table, T', is formed

by interchanging the two columns of T. The resulting Table 3.7(b) corresponds to the

relation R-^1 .Theorem 3 says that R is symmetric if and only if T and T' have the same

rows. The order of the rows may be different, but exactly the same rows are present. Since

any n-ary relation is a set of ordered n-tuples for some n E N, the order in which the

n-tuples are written in the table does not matter.

Table 3.7 IsMarriedTo (a) and IsMarriedTo^1

(b) Relations

T T'

John Mary Mary John

Mary John John Mary

Peter Elaine Elaine Peter

Elaine Peter Peter Elaine

Maude Harold Harold Maude

Harold Maude Maude Harold

(a) (b)

An examination of the two tables shows that T = T'.

Example 4.

(a) For any set X, equality is a symmetric, antisymmetric, and reflexive relation
on X.