Composition of Relations

Let A, B, and C be sets, and let R be a relation from A to B and let S be a relation from B to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a relation from A to C indicated by R◦S and defined by:

1. a (R◦S)c if for some b ∈ B we have aRb and bSc.   
2. is,   
3. R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}   

The relation R◦S is known the composition of R and S; it is sometimes denoted simply by RS.

Let R is a relation on a set A, that is, R is a relation from a set A to itself. Then R◦R, the composition of R with itself, is always represented. Also, R◦R is sometimes denoted by R². Similarly, R³ = R²◦R = R◦R◦R, and so on. Thus Rⁿ is defined for all positive n.

Example1: Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R₁ from X to Y and R₂ from Y to Z.

 R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
 R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation (i) R₁ o R₂ (ii) R₁o R₁^-1

Solution:

(i) The composition relation R₁ o R₂ as shown in fig:

R₁ o R₂ = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R₁o R₁^-1 as shown in fig:

R₁o R₁^-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

Composition of Relations and Matrices

There is another way of finding R◦S. Let M_R and M_S denote respectively the matrix representations of the relations R and S. Then

Example

1. Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by  
2.     R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}  
3.     S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.  
4.   
5.         Find the matrices of the above relations.  
6. Use matrices to find the following composition of the relation R and S.  
7.   (i)RoS       (ii)RoR       (iii)SoR  

Solution: The matrices of the relation R and S are a shown in fig:

(i) To obtain the composition of relation R and S. First multiply M_R with M_S to obtain the matrix M_R x M_S as shown in fig:

The non zero entries in the matrix M_R x M_S tells the elements related in RoS. So,

Hence the composition R o S of the relation R and S is

1. R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.  

(ii) First, multiply the matrix M_R by itself, as shown in fig

Hence the composition R o R of the relation R and S is

1. R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}  

(iii) Multiply the matrix M_S with M_R to obtain the matrix M_S x M_R as shown in fig:

The non-zero entries in matrix M_S x M_R tells the elements related in S o R.

Hence the composition S o R of the relation S and R is

1. S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.