Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 2] RELATIONS 27

2.5Composition of Relations

LetA,BandCbe sets, and letRbe a relation fromAtoBand letSbe a relation fromBtoC. That is,Ris
a subset ofA×BandSis a subset ofB×C. ThenRandSgive rise to a relation fromAtoCdenoted byR◦S
and defined by:
a(R◦S)cif for someb∈Bwe haveaRbandbSc.

That is ,
R◦S={(a, c)|there existsb∈B for which(a, b)∈Rand(b, c)∈S}

The relationR◦Sis called thecompositionofRandS; it is sometimes denoted simply byRS.
SupposeRis a relation on a setA, that is,Ris a relation from a setAto itself. ThenR◦R,the composition
ofRwithitself, is always defined. Also,R◦Ris sometimes denoted byR^2. Similarly,R^3 =R^2 ◦R=R◦R◦R,
and so on. ThusRnis defined for all positiven.

Warning:Many texts denote the composition of relationsRandSbyS◦Rrather thanR◦S. This is done in order
to conform with the usual use ofg◦fto denote the composition offandgwherefandgare functions. Thus the
reader may have to adjust this notation when using this text as a supplement with another text. However, when a
relationRis composed with itself, then the meaning ofR◦Ris unambiguous.

EXAMPLE 2.4 LetA={ 1 , 2 , 3 , 4 },B={a, b, c, d},C={x, y, z}and let

R={( 1 , a), ( 2 , d), ( 3 , a), ( 3 , b), ( 3 ,d)} and S={(b, x), (b, z), (c, y), (d, z)}

Consider the arrow diagrams ofRandSas in Fig. 2-4. Observe that there is an arrow from 2 todwhich is followed
by an arrow fromdtoz. We can view these two arrows as a “path” which “connects” the element 2∈Ato the
elementz∈C. Thus:
2 (R◦S)z since 2 RdanddSz

Similarly there is a path from 3 toxand a path from 3 toz. Hence

3 (R◦S)x and 3(R◦S)z

No other element ofAis connected to an element ofC. Accordingly,

R◦S={( 2 , z), ( 3 , x), ( 3 ,z)}

Our first theorem tells us that composition of relations is associative.

Theorem 2.1: LetA,B,CandDbe sets. SupposeRis a relation fromAtoB,Sis a relation fromBtoC, and
Tis a relation fromCtoD. Then

(R◦S)◦T=R◦(S◦T)

We prove this theorem in Problem 2.8.

Fig. 2-4