Discrete Mathematics for Computer Science

164 CHAPTER 3 Relations

(x, y) E < if and only if (y, x) E >

The formalization of this property is stated next.

Definition 3. Let R be a binary relation. The inverse of R, denoted R-1, is

{(x, y) :(y,x) e R}

Producing the inverse R^1 of a relation R can be thought of as performing an operation

on R. This operation is known as taking the inverse of R, or as inverting R.

Example 7. Recall the relation IsParentOf in Example 2. Thus,

IsParentOf^1 = {(Elaine, Mary), (Elaine, John), (Maude, Mary),

(Maude, John), (George, Peter), (George, Elaine),

(Elizabeth, Maude), (Elizabeth, Harold))

The relation IsParentOf-^1 expresses the fact that one person is the child of an-

other, so it is natural to denote this relation by a new name, such as IsChildOf. Hence,

using the new name for IsParentOf-^1 , (a, b) E IsParentOf if and only if (b, a) e

IsChildOf. E

Example 8.

GtN• = ((1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0) .... I

Gt 1 = {(0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 3), (0, 4) .... I

Clearly, Gt-1 is the relation Lt, since a > b if and only if b < a. U

Theorem 2. Let R and S be binary relations on a set X. Then,

(a) (R-l) -1- R.

(b) (RU S)- =R-^1 U S-1.

(c) IfS C R, then S-1 c R-^1.

Proof. (a) For any x, y E X,

(X, y) E (R-l)-1 ۥ(y, x) E R-1

¢ (x, y) E R

Hence, (R-^1 )-^1 = R

(b) For any x, y E X,

(x,y) E (RUSS)1 .•(y,x) E RUS

ۥ'(y,x)ER or (y,x)ES

i(x, y) E R-^1 U or (x, y) S-1

ۥ(X, y) E R-' U S-1