Operations on Binary Relations
165
Hence, (R U S)1 - R1 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 IsGrandparentOf 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 IsParentOf. 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
165
Hence, (R U S)1 - R1 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 IsGrandparentOf 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 IsParentOf. 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