# Composition of Relations

Let R $\subseteq$ A $\times$ B, S $\subseteq$ B $\times$ C, be two relations. Then, composition of the relations R and S denoted by SoR $\subseteq$ A $\times$ C and is defined by (a, c) $\in$ SoR iff $\exists$b $\in$ B s.t.

(a, b) $\in$ R, (b, c) $in$ S

e.g., Let A = {1, 2, 3}, B = {a, b, c, d}, C = {$\alpha$, $\beta$, $\gamma$}

R $\subseteq$ (A $\times$ B) = {(1, a), (1, c), (2, d)}

S $\subseteq$ (B $\times$ C) = {(a, $\alpha$), (c, $\gamma$), (d, $\beta$)}

Then, SoR $\subseteq$ (A $\times$ C) = {(1, $\alpha$), (1, $\gamma$), (2, $\beta$)}

Note

• One should be careful in computing the relation RoS. Actually, SoR starts with R and RoS starts with S
• In general, SoR $\neq$ RoS
• $(SoR)^{-1}=R^{-1}oS^{-1}$, known as reversal rule.
Simple Problem 1

If R is a relation from a set A to the set B and S is a relation from B to C, then the relation SoR
(a) is from C to A
(b) is from A to C
(c) does not exist
(d) None of these

Given,  R $\subseteq$ (A $\times$ B) and S $\subseteq$ (B $\times$ C)

We, have

SoR $\subseteq$ (A $\times$ C)

So, SoR $\subseteq$ (A $\times$ B)

Simple Problem 2

Let a relation R be defined by R = {(4, 5), (1, 4), (4, 6), (7, 6), (3, 7)}. The relation $RoR^{-1}$ is given by
(a) {(1, 1), (4, 4), (7, 4), (4, 7), (7, 7)}
(b) {(1, 1), (4, 4), (4, 7), (7, 4), (7, 7), (3, 3)}
(c) {(1, 5), (1, 6), (3, 6)}
(d) None of the above

So, $R^{-1}$ = {(5, 4), (4, 1), (6, 4), (6, 7), (7, 3)}
⇒ $R^{-1}$oR= {(4, 4), (1, 1), (4, 7), (7, 4), (7, 7), (3, 3)}