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 IsParentOf1 expresses the fact that one person is the child of another, so it is natural to denote this relation by a new name, such as IsChildOf. Hence,
using the new name for IsParentOf1 , (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)- =R1 U S-1.
(c) IfS C R, then S-1 c R1 .
Proof. (a) For any x, y E X,
(X, y) E (R-l)-1 ۥ(y, x) E R-1
¢ (x, y) E R
Hence, (R1 )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 R1 or (x, y)
U
S-1
ۥ(X, y) E R-' U S-1