Calculus

Set Theory

Set Theory Logo

Composition of Relations

We assume that the reader is already familiar with the basic operations on binary relations such as the union or intersection of relations. Now we consider one more important operation called the composition of relations.

Definition

Let \(A, B\) and \(C\) be three sets. Suppose that \(R\) is a relation from \(A\) to \(B,\) and \(S\) is a relation from \(B\) to \(C.\)

Composition of two binary relations
Figure 1.

The composition of \(R\) and \(S,\) denoted by \(S \circ R,\) is a binary relation from \(A\) to \(C,\) if and only if there is a \(b \in B\) such that \(aRb\) and \(bSc.\) Formally the composition \(S \circ R\) can be written as

\[{S \circ R \text{ = }}\kern0pt{\left\{ {\left( {a,c} \right) \mid {\exists b \in B}: {aRb} \land {bSc} } \right\},}\]

where \(a \in A\) and \(c \in C.\)

The composition of binary relations is associative, but not commutative.

To denote the composition of relations \(R\) and \(S, \) some authors use the notation \(R \circ S\) instead of \(S \circ R.\) This is, however, inconsistent with the composition of functions where the resulting function is denoted by

\[y = f\left( {g\left( x \right)} \right) = \left( {f \circ g} \right)\left( x \right).\]

The composition of relations \(R\) and \(S\) is often thought as their multiplication and is written as

\[S \circ R = RS.\]

Powers of Binary Relations

If a relation \(R\) is defined on a set \(A,\) it can always be composed with itself. So, we may have

\[R \circ R = {R^2},\]

\[R \circ R \circ R = {R^3},\]

\[\underbrace {R \circ R \circ \ldots \circ R}_n = {R^n}.\]

Composition of Relations in Matrix Form

Suppose the relations \(R\) and \(S\) are defined by their matrices \(M_R\) and \(M_S.\) Then the composition of relations \(S \circ R = RS\) is represented by the matrix product of \(M_R\) and \(M_S:\)

\[{M_{S \circ R}} = {M_{RS}} = {M_R} \times {M_S}.\]

Recall that \(M_R\) and \(M_S\) are logical (Boolean) matrices consisting of the elements \(0\) and \(1.\) The multiplication of logical matrices is performed as usual, except Boolean arithmetic is used, which implies the following rules:

\[{0 + 0 = 0,\;\;}\kern0pt{1 + 0 = 0 + 1 = 1,\;\;}\kern0pt{1 + 1 = 1;}\]

\[{0 \times 0 = 0,\;\;}\kern0pt{1 \times 0 = 0 \times 1 = 0,\;\;}\kern0pt{1 \times 1 = 1.}\]

Example:

Consider the sets \(A = \left\{ {a,b} \right\},\) \(B = \left\{ {0,1,2} \right\}, \) and \(C = \left\{ {x,y} \right\}.\) The relation \(R\) between sets \(A\) and \(B\) is given by

\[R = \left\{ {\left( {a,0} \right),\left( {a,2} \right),\left( {b,1} \right)} \right\}.\]

The relation \(S\) between sets \(B\) and \(C\) is defined as

\[S = \left\{ {\left( {0,x} \right),\left( {0,y} \right),\left( {1,y} \right),\left( {2,y} \right)} \right\}.\]

To determine the composition of the relations \(R\) and \(S,\) we represent the relations by their matrices:

\[{{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&0 \end{array}} \right],\;\;}\kern0pt{{M_S} = \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1\\ 0&1 \end{array}} \right].}\]

The matrix of the composition of relations \(M_{S \circ R}\) is calculated as the product of matrices \(M_R\) and \(M_S:\)

\[{{M_{S \circ R}} = {M_R} \times {M_S} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&0 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1\\ 0&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} {1 + 0 + 0}&{1 + 0 + 1}\\ {0 + 0 + 0}&{0 + 1 + 0} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1\\ 0&1 \end{array}} \right].}\]

In roster form, the composition of relations \(S \circ R\) is written as

\[S \circ R = \left\{ {\left( {a,x} \right),\left( {a,y} \right),\left( {b,y} \right)} \right\}.\]


Solved Problems

Click or tap a problem to see the solution.

Example 1

The relation \(R\) on the set of real numbers \(\mathbb{R}\) is defined by \[R = \left\{ {\left( {x,y} \right) \mid y = x – 1} \right\}.\] Find the composition of relations \(R^2.\)

Example 2

The relation \(S\) on the set of real numbers \(\mathbb{R}\) is defined by \[S = \left\{ {\left( {x,y} \right) \mid y = x^2 + 1} \right\}.\] Find the composition of relations \(S^2.\)

Example 3

Given the set \(A = \left\{ {0,1,2} \right\}\) with the relations \(R = \left\{ {\left( {0,1} \right),\left( {0,2} \right),\left( {1,1} \right),\left( {2,0} \right)} \right\}\) and \(S = \left\{ {\left( {0,0} \right),\left( {0,2} \right),\left( {1,0} \right),\left( {1,1} \right)} \right\}.\) Find the compositions \(S \circ R\) and \(R \circ S.\)

Example 4

Given the set \(A = \left\{ {a,b,c} \right\}\) with the relations \(R = \left\{ {\left( {a,a} \right),\left( {a,c} \right),\left( {b,a} \right),\left( {c,b} \right)} \right\}\) and \(S = \left\{ {\left( {a,b} \right),\left( {b,c} \right),\left( {c,c} \right)} \right\}.\) Find the composition \({S^{-1}} \circ {R^{-1}}.\)

Example 5

Consider the set \(A = \left\{ {1,2,3} \right\}\) with the relations \(R = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {3,1} \right)} \right\}\) and \(S = \left\{ {\left( {1,2} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {3,3} \right)} \right\}.\) Calculate the composition \({R \circ S}\) in matrix form.

Example 6

Consider the set \(X = \left\{ {x,y,z} \right\}\) with the relation \(R = \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {b,c} \right),} \right.\) \(\kern-2pt\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}.\) Calculate the combined relation \({R^2 \cap R^{-1}}\) in matrix form.

Example 1.

The relation \(R\) on the set of real numbers \(\mathbb{R}\) is defined by \[R = \left\{ {\left( {x,y} \right) \mid y = x – 1} \right\}.\] Find the composition of relations \(R^2.\)

Solution.

By definition, the composition \(R^2\) is the relation given by the following property:

\[{{R^2} = R \circ R }={ \left\{ {\left( {x,z} \right) \mid \exists y \in R : xRy \land yRz} \right\},}\]

where

\[{xRy = \left\{ {\left( {x,y} \right) \mid y = x – 1} \right\},\;\;}\kern0pt{yRz = \left\{ {\left( {y,z} \right) \mid z = y – 1} \right\}.}\]

To determine the composed relation \(xRz,\) we solve the system of equations:

\[{\left\{ \begin{array}{l} y = x – 1\\ z = y – 1 \end{array} \right.,}\;\; \Rightarrow {z = \left( {x – 1} \right) – 1 }={ x – 2.}\]

Hence, the composition \(R^2\) is given by

\[{R^2} = \left\{ {\left( {x,z} \right) \mid z = x – 2} \right\}.\]

It is clear that the composition \(R^n\) is written in the form

\[{R^n} = \left\{ {\left( {x,z} \right) \mid z = x – n} \right\}.\]

Example 2.

The relation \(S\) on the set of real numbers \(\mathbb{R}\) is defined by \[S = \left\{ {\left( {x,y} \right) \mid y = x^2 + 1} \right\}.\] Find the composition of relations \(S^2.\)

Solution.

The composition \(S^2\) is given by the property:

\[{{S^2} = S \circ S }={ \left\{ {\left( {x,z} \right) \mid \exists y \in S : xSy \land ySz} \right\},}\]

where

\[{xSy = \left\{ {\left( {x,y} \right) \mid y = x^2 + 1} \right\},\;\;}\kern0pt{ySz = \left\{ {\left( {y,z} \right) \mid z = y^2 + 1} \right\}.}\]

We eliminate the variable \(y\) in the second relation by substituting the expression \(y = x^2 +1\) from the first relation:

\[{z = {y^2} + 1 }={ {\left( {{x^2} + 1} \right)^2} + 1 }={ {x^4} + 2{x^2} + 2.}\]

So we have:

\[{{S^2} \text{ = }}{\left\{ {\left( {x,z} \right) \mid z = {x^4} + 2{x^2} + 2} \right\}.}\]

Example 3.

Given the set \(A = \left\{ {0,1,2} \right\}\) with the relations \(R = \left\{ {\left( {0,1} \right),\left( {0,2} \right),\left( {1,1} \right),\left( {2,0} \right)} \right\}\) and \(S = \left\{ {\left( {0,0} \right),\left( {0,2} \right),\left( {1,0} \right),\left( {1,1} \right)} \right\}.\) Find the compositions \(S \circ R\) and \(R \circ S.\)

Solution.

  1. Consider the composition \(S \circ R.\) Recall the the first step in this composition is \(R\) and the second is \(S.\) The first element in \(R\) is \({\left( {0,1} \right)}.\) Look for pairs starting with \(1\) in \(S:\) \({\left( {1,0} \right)}\) and \({\left( {1,1} \right)}.\) Therefore \({\left( {0,1} \right)}\) in \(R\) combined with \({\left( {1,0} \right)}\) in \(S\) gives \({\left( {0,0} \right)}.\) Similarly, \({\left( {0,1} \right)}\) in \(R\) combined with \({\left( {1,1} \right)}\) in \(S\) gives \({\left( {0,1} \right)}.\) We use the same approach to match all other elements from \(R.\) As a result, we find all pairs belonging to the composition \(S \circ R:\) \[{S \circ R \text{ = }}\kern0pt{\left\{ {\left( {0,0} \right),\left( {0,1} \right),}\right.}\kern0pt{\left.{\left( {1,0} \right),\left( {1,1} \right),}\right.}\kern0pt{\left.{\left( {2,0} \right),\left( {2,2} \right)} \right\}.}\]
  2. The composition \(R \circ S\) implies that \(S\) is performed in the first step and \(R\) is performed in the second step. Consider the first element of the relation \(S:\) \({\left( {0,0} \right)}.\) We see that it matches to the following pairs in \(R:\) \({\left( {0,1} \right)}\) and \({\left( {0,2} \right)}.\) Hence, the composition \(R \circ S\) contains the elements \({\left( {0,1} \right)}\) and \({\left( {0,2} \right)}.\) Continuing in this way, we find that \[{R \circ S \text{ = }}\kern0pt{\left\{ {\left( {0,0} \right),\left( {0,1} \right),}\right.}\kern0pt{\left.{\left( {0,2} \right),\left( {1,1} \right),}\right.}\kern0pt{\left.{\left( {1,2} \right)} \right\}.}\]
  3. As it can be seen, the composition of relations is not commutative.

Example 4.

Given the set \(A = \left\{ {a,b,c} \right\}\) with the relations \(R = \left\{ {\left( {a,a} \right),\left( {a,c} \right),\left( {b,a} \right),\left( {c,b} \right)} \right\}\) and \(S = \left\{ {\left( {a,b} \right),\left( {b,c} \right),\left( {c,c} \right)} \right\}.\) Find the composition \({S^{-1}} \circ {R^{-1}}.\)

Solution.

First we write the inverse relations \(R^{-1}\) and \(S^{-1}:\)

\[{{R^{ – 1}} \text{ = }}\kern0pt{\left\{ {\left( {a,a} \right),\left( {c,a} \right),\left( {a,b} \right),\left( {b,c} \right)} \right\} }={ \left\{ {\left( {a,a} \right),\left( {a,b} \right),\left( {b,c} \right),\left( {c,a} \right)} \right\};}\]

\[{S^{ – 1}} = \left\{ {\left( {b,a} \right),\left( {c,b} \right),\left( {c,c} \right)} \right\}.\]

The first element in \(R^{-1}\) is \({\left( {a,a} \right)}.\) It has no match to the relation \(S^{-1}.\)

Take the second element in \(R^{-1}:\) \({\left( {a,b} \right)}.\) It matches to the pair \({\left( {b,a} \right)}\) in \(S^{-1},\) producing the composed pair \({\left( {a,a} \right)}\) for \(S^{-1} \circ R^{-1}.\)

Similarly, we find that \({\left( {b,c} \right)}\) in \(R^{-1}\) combined with \({\left( {c,b} \right)}\) in \(S^{-1}\) gives \({\left( {b,b} \right)}.\) The same element in \(R^{-1}\) can also be combined with \({\left( {c,c} \right)}\) in \(S^{-1},\) which gives the element \({\left( {b,c} \right)}\) for the composition \(S^{-1} \circ R^{-1}.\)

The last pair \({\left( {c,a} \right)}\) in \(R^{-1}\) has no match in \(S^{-1}.\) Thus, the composition of relations \(S^{-1} \circ R^{-1}\) contains the following elements:

\[{{S^{ – 1}} \circ {R^{ – 1}} \text{ = }}\kern0pt{\left\{ {\left( {a,a} \right),\left( {b,b} \right),\left( {b,c} \right)} \right\}.}\]

Example 5.

Consider the set \(A = \left\{ {1,2,3} \right\}\) with the relations \(R = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {3,1} \right)} \right\}\) and \(S = \left\{ {\left( {1,2} \right),\left( {2,1} \right),} \right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {3,3} \right)} \right\}.\) Calculate the composition \({R \circ S}\) in matrix form.

Solution.

The relations \(R\) and \(S\) are represented by the following matrices:

\[{{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 1&1&0\\ 1&0&0 \end{array}} \right],\;\;}\kern0pt{{M_S} = \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&1&0\\ 0&0&1 \end{array}} \right].}\]

To find the composition of relations \(R \circ S,\) we multiply the matrices \(M_S\) and \(M_R:\)

\[{{M_{R \circ S}} = {M_S} \times {M_R} }={ \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&1&0\\ 0&0&1 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 1&1&0\\ 1&0&0 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} {0 + 1 + 0}&{0 + 1 + 0}&{0 + 0 + 0}\\ {1 + 1 + 0}&{0 + 1 + 0}&{1 + 0 + 0}\\ {0 + 0 + 1}&{0 + 0 + 0}&{0 + 0 + 0} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1&0\\ 1&1&1\\ 1&0&0 \end{array}} \right].}\]

We used here the Boolean algebra when making the addition and multiplication operations.

Hence, the composition of relations \(R \circ S\) is given by

\[{R \circ S \text{ = }}\kern0pt{\left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}\kern0pt{\left.{\left( {2,1} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,3} \right),\left( {3,1} \right)} \right\}.}\]

Example 6.

Consider the set \(X = \left\{ {x,y,z} \right\}\) with the relation \(R = \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {b,c} \right),} \right.\) \(\kern-2pt\left.{\left( {c,b} \right),\left( {c,c} \right)} \right\}.\) Calculate the combined relation \({R^2 \cap R^{-1}}\) in matrix form.

Solution.

First, we convert the relation \(R\) to matrix form:

\[{M_R} = \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&0&1\\ 0&0&1 \end{array}} \right].\]

Compute the composition of relations \(R^2\) using matrix multiplication:

\[{{M_{{R^2}}} = {M_R} \times {M_R} }={ \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&0&1\\ 0&0&1 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&0&1\\ 0&0&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} {0 + 1 + 0}&{0 + 0 + 0}&{0 + 1 + 0}\\ {0 + 0 + 0}&{1 + 0 + 0}&{0 + 0 + 1}\\ {0 + 0 + 0}&{0 + 0 + 0}&{0 + 0 + 1} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&1\\ 0&0&1 \end{array}} \right].}\]

The inverse (or converse) relation \(R^{-1}\) is represented by the following matrix:

\[{M_{{R^{ – 1}}}} = \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&0&0\\ 0&1&1 \end{array}} \right].\]

Now we can find the intersection of the relations \(R^2\) and \(R^{-1}.\) Remember that when calculating the intersection of relations, we apply Hadamard matrix multiplication, which is different from the regular matrix multiplication. So, we multiply the corresponding elements of the matrices \(M_{R^2}\) and \(M_{R^{-1}}:\)

\[{{M_{{R^2} \cap {R^{ – 1}}}} = {M_{{R^2}}} * {M_{{R^{ – 1}}}} }={ \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&1\\ 0&0&1 \end{array}} \right] }*{ \left[ {\begin{array}{*{20}{c}} 0&1&0\\ 1&0&0\\ 0&1&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 0&0&0\\ 0&0&1 \end{array}} \right].}\]

Thus, the final relation contains only one ordered pair:

\[{R^2} \cap {R^{ – 1}} = \left\{ \left( {c,c} \right) \right\} .\]