Calculus

Set Theory

Set Theory Logo

Composition of Relations

Solved Problems

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\},\;\;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\},\;\;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} = \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 = \left\{ {\left( {0,0} \right),\left( {0,1} \right),\left( {1,0} \right),\left( {1,1} \right),\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 = \left\{ {\left( {0,0} \right),\left( {0,1} \right),\left( {0,2} \right),\left( {1,1} \right),\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}} = \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}} = \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],\;\;{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 = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right)} \right\}.\]

Example 6.

Consider the set \(A = \left\{ {a,b,c} \right\}\) with the relation \(R = \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {b,c} \right),} \right.\) \(\kern-2pt\left.{\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\}.\]
Page 1 Page 2