Operations on Binary Relations 165
Hence, (R U S)-^1 - R-^1 U S-1
(c) This proof is left as an exercise for the reader. 0
3.2.2 Composition
The composition of two relations produces a new relation. Some very familiar examples of
relations arise in just this way. For example, we shall soon see that the relation IsGrand-
parentOf is the composition of IsParentOf with itself.
Definition 4. Let R and S be binary relations on the set X. The composition of R and S,
denoted R o S, is defined as follows:
RoS = {(x,y) EX2 :forsome zEX,(x,z) E S and (z,y) E R}
The reader may consider the notation R o S to be backward and think that S o R would
be more natural. The motivation for writing R o S will become obvious in the next chapter,
however, when we discuss the composition of functions. Note that the composition of S and
R, denoted as S o R, generally creates a different set of ordered pairs than the composition
R o S of R and S.
Example 9. The family tree diagram shown in Figure 3.2 can be used to define Is-
ParentOf. Since (Mary, Elaine) E IsParentOf and (Elaine, George) E IsParentOf (Mary,
George) E IsParentOf o IsParentOf. Working out all the possibilities for this composition
gives
IsParentOf o IsParentOf = {(Mary, George), (John, George),
(Mary, Elizabeth), (John, Elizabeth)) U
Clearly, (a, b) E IsParentOf o IsParentOf means that a is the grandparent of b. As
another example of composition, convince yourself that
IsCousinOf = IsParentOf o IsSiblingOf o IsChildOf
You should be able to show that George and Elizabeth in Figure 3.2 are cousins.
The composition of a relation R on a set X with the equality relation on X should
always gives the relation R. We prove this in Theorem 3.
Theorem 3. Let X be any set and R be any binary relation on X. Then,
R = Idx o R = R o Idx
Proof. The proofs of these equalities are similar, so only the proof that R = IdX o R will
be given. To do this proof, we show that IdxoR C R and R C Idx o R. The proof follows
Template 1.5 (Set Equality).
First, suppose that (x, y) E Idx o R. Then, by the definition of composition, there is
a z E X with (x, z) E R and (z, y) E Idx. Since (z, y) E Idx, we have z = y. Therefore,
(x, z) = (x, y). Hence, (x, y) E R.
Second, suppose that (x, y) E R. Now, (y, y) E Idx, so (x, y) E Idx o R. U
