Calculus

Set Theory

Set Theory Logo

Closures of Relations

Let \(R\) be a binary relation on a set \(A.\) The relation \(R\) may or may not have some property \(\mathbf{P},\) such as reflexivity, symmetry, or transitivity.

Suppose, for example, that \(R\) is not reflexive. If so, we could add ordered pairs to this relation to make it reflexive. The smallest reflexive relation \(R^{+}\) that includes \(R\) is called the reflexive closure of \(R.\)

In general, if a relation \(R^{+}\) with property \(\mathbf{P}\) contains \(R\) such that

  • \(R^{+}\) is a subset of every relation with property \(\mathbf{P}\) containing \(R,\)

then \(R^{+}\) is a closure of \(R\) with respect to property \(\mathbf{P}.\)

There are many ways to denote closures of relations. Besides the common notations like \(R^{+},\) the reflexive closure of a relation \(R\) may be denoted by

\[{{R^r},\;{R_r},\;R_r^+,\;}\kern0pt{r\left( R \right),\;}\kern0pt{cl_{ref}\left( R \right),\;}\kern0pt{refc\left( R \right),\text{ etc.}}\]

For the symmetric closure, the following notations can be used:

\[{{R^s},\;{R_s},\;R_s^+,\;}\kern0pt{s\left( R \right),\;}\kern0pt{cl_{sym}\left( R \right),\;}\kern0pt{symc\left( R \right),\text{ etc.}}\]

Respectively, the transitive closure is denoted by

\[{{R^t},\;{R_t},\;R_t^+,\;}\kern0pt{t\left( R \right),\;}\kern0pt{cl_{trn}\left( R \right),\;}\kern0pt{tr\left( R \right),\text{ etc.}}\]

We shall use the following notations throughout this section: \(R^{+},\) \(r\left( R \right),\) \(s\left( R \right),\) \(t\left( R \right).\)

Note that it may not be possible to build a closure for any relation property. For example, if a binary relation \(R\) has an ordered pair of kind \(\left( {a,a} \right),\) there is no extension \(R^+,\) which makes this relation irreflexive.

Now let us consider the most popular closures of relations in more detail.

Reflexive Closure

The reflexive closure of a binary relation \(R\) on a set \(A\) is defined as the smallest reflexive relation \(r\left( R \right)\) on \(A\) that contains \(R.\) The smallest relation means that it has the fewest number of ordered pairs.

The reflexive closure \(r\left( R \right)\) is obtained by adding the elements \(\left( {a,a} \right)\) to the original relation \(R\) for all \(a \in A.\) Formally, we can write

\[r\left( R \right) = R \cup I,\]

where \(I\) is the identity relation, which is given by

\[I = \left\{ {\left( {a,a} \right) \mid \forall a \in A} \right\}.\]

Example:

Consider the relation \(R = \left\{ {\left( {1,2} \right),\left( {2,4} \right),}\right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {4,2} \right)} \right\}\,\) on the set \(A = \left\{ {1,2,3,4} \right\}.\) \(R\) is not reflexive. To make it reflexive, we add all missing diagonal elements:

\[{r\left( R \right) = R \cup I }={ \left\{ {\left( {1,2} \right),\left( {2,4} \right),{\left( {3,3} \right)},\left( {4,2} \right)} \right\} }\cup{ \left\{ {{\left( \color{red}{1,1} \right)},{\left( \color{red}{2,2} \right)},{\left( \color{red}{3,3} \right)},{\left( \color{red}{4,4} \right)}} \right\} }={ \left\{ {{\left( \color{red}{1,1} \right)},\left( {1,2} \right),{\left( \color{red}{2,2} \right)},}\right.}\kern0pt{\left.{\left( {2,4} \right),{\left( {3,3} \right)},\left( {4,2} \right),}\right.}\kern0pt{\left.{{\left( \color{red}{4,4} \right)}} \right\}.}\]

The problem can also be solved in matrix form. Recall that the union of relations in matrix form is represented by the sum of matrices, and the addition operation is performed according to the Boolean arithmetic rules. So, the matrix of the reflexive closure of \(R\) is given by

\[{{M_{r\left( R \right)}} = {M_R} + {M_I} }={ \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&0&0\\ 0&\color{red}{1}&0&0\\ 0&0&\color{red}{1}&0\\ 0&0&0&\color{red}{1} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} \color{red}{1}&1&0&0\\ 0&\color{red}{1}&0&1\\ 0&0&1&0\\ 0&1&0&\color{red}{1} \end{array}} \right].}\]

The digraph of the reflexive closure \(r\left( R \right)\) is obtained from the digraph of the original relation \(R\) by adding missing self-loops to all vertices.

Digraph of the reflexive closure of a relation
Figure 1.

Symmetric Closure

The symmetric closure of a relation \(R\) on a set \(A\) is defined as the smallest symmetric relation \(s\left( R \right)\) on \(A\) that contains \(R.\)

The symmetric closure \(s\left( R \right)\) is obtained by adding the elements \(\left( {b,a} \right)\) to the relation \(R\) for each pair \(\left( {a,b} \right) \in R.\) In terms of relation operations,

\[{s\left( R \right)}={ R \cup {R^{ – 1}} } = { R \cup {R^T} ,}\]

where \(R^{-1} = R^T\) denotes the inverse of \(R\) (also called the converse or transpose relation).

Example:

Let \(R = \left\{ {\left( {1,2} \right),\left( {1,3} \right),}\right.\) \(\kern-2pt\left.{\left( {2,2} \right),\left( {2,4} \right),\left( {4,3} \right)} \right\}\,\) be a binary relation on the set \(A = \left\{ {1,2,3,4} \right\}.\) The relation \(R\) is not symmetric. It contains \(4\) non-reflexive elements: \(\left( {1,2} \right),\) \(\left( {1,3} \right),\) \(\left( {2,4} \right),\) and \(\left( {4,3} \right),\) which do not have a reverse pair. So, to make \(R\) symmetric, we need to add the following missing reverse elements: \(\left(\color{red}{2,1} \right),\) \(\left(\color{red}{3,1} \right),\) \(\left(\color{red}{4,2} \right),\) and \(\left(\color{red}{3,4} \right):\)

\[{s\left( R \right)}={ \left\{ {\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {4,3} \right)} \right\} }\cup{ \left\{ {\left( \color{red}{2,1} \right),\left( \color{red}{3,1} \right),}\right.}\kern0pt{\left.{\left( \color{red}{4,2} \right),\left( \color{red}{3,4} \right)} \right\} }={ \left\{ {\left( {1,2} \right),\left( {1,3} \right),\left( \color{red}{2,1} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,4} \right),\left( \color{red}{3,1} \right),}\right.}\kern0pt{\left.{\left( \color{red}{3,4} \right),\left( \color{red}{4,2} \right),\left( {4,3} \right)} \right\}.}\]

We can also find the solution in matrix form. The matrices of the relations \(R\) and \(R^{-1}\) are given by

\[{M_R = \left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&1&0&1\\ 0&0&0&0\\ 0&0&1&0 \end{array}} \right],\;\;}\kern0pt{{M_{R^{ – 1}}} = \left[ {\begin{array}{*{20}{c}} 0&0&0&0\\ \color{red}{1}&1&0&0\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&\color{red}{1}&0&0 \end{array}} \right].}\]

Now we calculate the sum of the matrices \(M_R\) and \(M_{R^{-1}}:\)

\[{{M_{s\left( R \right)}} = {M_R} + {M_{{R^{ – 1}}}} }={ \left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&1&0&1\\ 0&0&0&0\\ 0&0&1&0 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} 0&0&0&0\\ \color{red}{1}&1&0&0\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&\color{red}{1}&0&0 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ \color{red}{1}&1&0&1\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&\color{red}{1}&1&0 \end{array}} \right].}\]

The digraph of the symmetric closure \(s\left( R \right)\) is obtained from the digraph of the original relation \(R\) by adding the edge in the reverse direction (if none already exists) for each edge in the digraph for \(R.\)

Digraph of the symmetric closure of a relation
Figure 2.

Transitive Closure

The transitive closure of a binary relation \(R\) on a set \(A\) is the smallest transitive relation \(t\left( R \right)\) on \(A\) containing \(R.\)

The transitive closure is more complex than the reflexive or symmetric closures. To describe how to construct a transitive closure, we need to introduce two new concepts – the paths and the connectivity relation.

Paths

Suppose that \(R\) is a relation on a set \(A.\) Consider two elements \(a \in A,\) \(b \in A.\) A path from \(a\) to \(b\) of length \(n\) is a sequence of ordered pairs

\[{\left( {a,{x_1}} \right),\left( {{x_1},{x_2}} \right),\left( {{x_2},{x_3}} \right), \ldots ,}\kern0pt{\left( {{x_{n – 1}},b} \right)},\]

in the relation \(R,\) where \(n\) is nonnegative integer.

Example:

Let \(R = \left\{ {\left( {1,2} \right),\left( {2,4} \right),\left( {4,3} \right)} \right\}\) be a relation on set \(A = \left\{ {1,2,3,4} \right\}.\) All the pairs \({\left( {1,2} \right)},\) \({\left( {2,4} \right)},\) \({\left( {4,3} \right)}\) are the paths of length \(n = 1.\) Besides that, \(R\) has the paths of length \(n = 2:\)

\[{\left( {1,2} \right),\left( {2,4} \right) \text{ and }}\kern0pt{ \left( {2,4} \right),\left( {4,3} \right).}\]

It can also be seen that the relation \(R\) itself is a path of length \(n = 3.\)

Theorem:

If \(R\) is a relation on a set \(A\) and \(a \in A,\) \(b \in A,\) then there is a path of length \(n\) from \(a\) to \(b\) if and only if \(\left( {a,b} \right) \in {R^n}\) for every positive integer \(n.\)

The theorem can be proved by mathematical induction.

Connectivity Relation

The connectivity relation of \(R,\) denoted \(R^{*},\) consists of all ordered pairs \(\left( {a,b} \right)\) such that there is a path (of any length) in \(R\) from \(a\) to \(b.\)

The connectivity relation \(R^{*}\) is the union of all the sets \(R^n:\)

\[{R^*} = \bigcup\limits_{n = 1}^\infty {{R^n}}.\]

If the relation \(R\) is defined on a finite set \(A\) with the cardinality \(\left| A \right| = n,\) then the connectivity relation is given by

\[{R^*} = R \cup {R^2} \cup {R^3} \cup \cdots \cup {R^n}.\]

It is clear that if \(R_{i-1} = R_i\) where \(i \le n,\) we can stop the computation process since the higher powers of \(R\) will not change the union operation.

Finding the Transitive Closure

The transitive closure \(t\left( R \right)\) of a relation \(R\) is equal to its connectivity relation \(R^{*}.\)

Example:

Consider the relation \(R = \left\{ {\left( {1,2} \right),\left( {2,2} \right),}\right.\) \(\kern-2pt\left.{\left( {2,3} \right),\left( {3,3} \right)} \right\}\,\) on the set \(A = \left\{ {1,2,3} \right\}.\) \(R\) is not transitive since we have \(\left( {1,2} \right) \in R,\) \(\left( {2,3} \right) \in R,\) but \(\left( {1,3} \right) \notin R.\) So we need to add \(\left( \color{red}{1,3} \right)\) to make \(R\) transitive:

\[{t\left( R \right) = R \cup \left\{ {\left( \color{red}{1,3} \right)} \right\} }={ \left\{ {\left( {1,2} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {3,3} \right)} \right\} }\cup{ \left\{ {\left( \color{red}{1,3} \right)} \right\} }={ \left\{ {\left( {1,2} \right),\left( \color{red}{1,3} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {3,3} \right)} \right\}.}\]

The digraph of a transitive closure contains all edges from \(a\) to \(b\) if there is a directed path from \(a\) to \(b.\) In our example, the transitive closure \(t\left( R \right)\) is represented by the following digraph:

Digraph of the symmetric closure of a relation
Figure 3.

We can also find the transitive closure of \(R\) in matrix form. The original relation \(R\) is defined by the matrix

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

The connectivity relation \(R^{*}\) is determined by the expression

\[{R^*} = R \cup {R^2} \cup {R^3}.\]

Calculate the matrix of the composition \(R^2:\)

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

Similarly we compute the matrix of the composition \(R^3:\)

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

As it can be seen, \({M_{{R^2}}} = {M_{{R^3}}}.\) Hence, the connectivity relation \(R^{*}\) can be found by the formula

\[{R^*} = R \cup {R^2}.\]

Using matrix representation, we have

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

where the matrix addition is performed based on the Boolean arithmetic rules.

Converting to roster form, we obtain the previous answer:

\[{t\left( R \right) = {R^*} }={ \left\{ {\left( {1,2} \right),\left( \color{red}{1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,3} \right),\left( {3,3} \right)} \right\}.}\]

The algorithm involving calculation of the connectivity relation has the running time proportional to \({O}\left( {{n^4}} \right).\) There are faster methods of finding transitive closures. For example, the Warshall algorithm allows to compute the transitive closure of a relation with the rate of \({O}\left( {{n^3}} \right).\)


Solved Problems

Click or tap a problem to see the solution.

Example 1

Let \(A = \left\{ {1,2,3,4} \right\}.\) A binary relation \(R\) on the set \(A\) is given by the digraph
A non-reflexive relation on a set of 4 elements.
Find the reflexive closure of \(R.\)

Example 2

Let \(B = \left\{ {1,2,3,4,5} \right\}.\) A binary relation \(S\) on the set \(B\) is given by the digraph
A non-symmetric relation on a set of 5 elements.
Find the symmetric closure of \(S.\)

Example 3

Let \(R = \left\{ {\left( {a,b} \right),\left( {b,c} \right),\left( {c,a} \right)} \right\}\) be a relation defined on the set \(A = \left\{ {a,b,c} \right\}.\) Find the reflexive closure of \(R^2\) using matrix representation.

Example 4

Let \(S = \left\{ {\left( {k,\ell} \right),\left( {k,n} \right),\left( {m,k} \right),} \right.\) \(\kern-2pt\left.{\left( {m,m} \right),\left( {n,\ell} \right)} \right\}\) be a relation defined on the set \(B = \left\{ {k,\ell,m,n} \right\}.\) Find the symmetric closure of \(S\) in matrix form.

Example 5

Find all paths of length \(3\) in the relation \(R.\)
A binary relation containing paths of length 3.

Example 6

Find all paths of length \(2\) in the relation \(S.\)
A binary relation containing paths of length 2.

Example 7

Let \(R = \left\{ {\left( {1,2} \right),\left( {2,3} \right),\left( {3,2} \right),\left( {4,1} \right)} \right\}\) be a binary relation on the set \(A = \left\{ {1,2,3,4} \right\}.\) Find the transitive closure of \(R.\)

Example 1.

Let \(A = \left\{ {1,2,3,4} \right\}.\) A binary relation \(R\) on the set \(A\) is given by the digraph
A non-reflexive relation on a set of 4 elements.
Find the reflexive closure of \(R.\)

Solution.

To build the reflexive closure of \(R,\) we just add the missing self-loops to all nodes of the digraph:

Reflexive closure of a binary relation on a set of 4 elements.
Figure 4.

In roster form, the reflexive closure \(r\left( R \right)\) is given by

\[{r\left( R \right)}={ \left\{ {\left( \color{red}{1,1} \right),\left( {1,2} \right),}\right.}\kern0pt{\left.{\left( {1,3} \right),\left( {1,4} \right),}\right.}\kern0pt{\left.{\left( {2,1} \right),\left( \color{red}{2,2} \right),}\right.}\kern0pt{\left.{\left( {3,1} \right),\left( {3,3} \right),}\right.}\kern0pt{\left.{\left( {3,4} \right),\left( \color{red}{4,4} \right)} \right\}.}\]

Example 2.

Let \(B = \left\{ {1,2,3,4,5} \right\}.\) A binary relation \(S\) on the set \(B\) is given by the digraph
A non-symmetric relation on a set of 5 elements.
Find the symmetric closure of \(S.\)

Solution.

To form the digraph of the symmetric closure, we simply add a new edge in the reverse direction (if none already exists) for each edge in the original digraph:

Symmetric closure of a binary relation on a set of 5 elements.
Figure 5.

The symmetric closure of \(S\) contains the following ordered pairs:

\[{s\left( S \right)}={ \left\{ {\left( {1,2} \right),\left( {1,5} \right),}\right.}\kern0pt{\left.{\left( \color{red}{2,1} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,4} \right),\left( {2,5} \right),}\right.}\kern0pt{\left.{\left( {3,4} \right),\left( \color{red}{3,5} \right),}\right.}\kern0pt{\left.{\left( {4,2} \right),\left( \color{red}{4,3} \right),}\right.}\kern0pt{\left.{\left( {4,4} \right),\left( \color{red}{5,1} \right),}\right.}\kern0pt{\left.{\left( \color{red}{5,2} \right),\left( {5,3} \right)} \right\}.}\]

Example 3.

Let \(R = \left\{ {\left( {a,b} \right),\left( {b,c} \right),\left( {c,a} \right)} \right\}\) be a relation defined on the set \(A = \left\{ {a,b,c} \right\}.\) Find the reflexive closure of \(R^2\) using matrix representation.

Solution.

Write the relation \(R\) is matrix form:

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

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

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

The reflexive closure of \(R^2\) is determined as the union of the relation \(R^2\) and the identity relation \(I:\)

\[r\left( {{R^2}} \right) = {R^2} \cup I,\]

so we have

\[{{M_{r\left( {{R^2}} \right)}} = {M_{{R^2}}} + {M_I} }={ \left[ {\begin{array}{*{20}{c}} 0&0&1\\ 0&0&0\\ 0&1&0 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&0\\ 0&\color{red}{1}&0\\ 0&0&\color{red}{1} \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&1\\ 0&\color{red}{1}&0\\ 0&1&\color{red}{1} \end{array}} \right].}\]

The reflexive closure \(r\left( {{R^2}} \right)\) in roster form is given by

\[{r\left( {{R^2}} \right) = \left\{ {\left( \color{red}{a,a} \right),\left( {a,c} \right),\left( \color{red}{b,b} \right),}\right.}\kern0pt{\left.{\left( {c,b} \right),\left( \color{red}{c,c} \right)} \right\}.}\]

Example 4.

Let \(S = \left\{ {\left( {k,\ell} \right),\left( {k,n} \right),\left( {m,k} \right),} \right.\) \(\kern-2pt\left.{\left( {m,m} \right),\left( {n,\ell} \right)} \right\}\) be a relation defined on the set \(B = \left\{ {k,\ell,m,n} \right\}.\) Find the symmetric closure of \(S\) in matrix form.

Solution.

The original relation \(S\) and the inverse relation \(S^{-1}\) are represented by the following matrices:

\[{{M_S} = \left[ {\begin{array}{*{20}{c}} 0&1&0&1\\ 0&0&0&0\\ 1&0&1&0\\ 0&1&0&0 \end{array}} \right],\;\;}\kern0pt{{M_{{S^{ – 1}}}} = \left[ {\begin{array}{*{20}{c}} 0&0&\color{red}{1}&0\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&0&1&0\\ \color{red}{1}&0&0&0 \end{array}} \right].}\]

The matrix of the symmetric closure \(s\left( S \right)\) is determined as the sum of the matrices \(M_S\) and \(M_{S^{-1}}:\)

\[{{M_{s\left( S \right)}} = {M_S} + {M_{{S^{ – 1}}}} }={ \left[ {\begin{array}{*{20}{c}} 0&1&0&1\\ 0&0&0&0\\ 1&0&1&0\\ 0&1&0&0 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} 0&0&\color{red}{1}&0\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&0&1&0\\ \color{red}{1}&0&0&0 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&1&\color{red}{1}&1\\ \color{red}{1}&0&0&\color{red}{1}\\ 1&0&1&0\\ \color{red}{1}&1&0&0 \end{array}} \right].}\]

Returning back to roster form, we have

\[{s\left( S \right) = \left\{ {\left( {k,l} \right),\left( \color{red}{k,m} \right),\left( {k,n} \right),}\right.}\kern0pt{\left.{\left( \color{red}{l,k} \right),\left( \color{red}{l,n} \right),}\right.}\kern0pt{\left.{\left( {m,k} \right),\left( {m,m} \right),}\right.}\kern0pt{\left.{\left( \color{red}{n,k} \right),\left( {n,l} \right)} \right\}.}\]

Example 5.

Find all paths of length \(3\) in the relation \(R.\)
A binary relation containing paths of length 3.

Solution.

The relation has \(6\) paths of length \(3:\)

\[\begin{array}{l} \left( {1,2} \right),\left( {2,4} \right),\left( {4,2} \right)\\ \left( {1,3} \right),\left( {3,4} \right),\left( {4,2} \right)\\ \left( {1,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\ \left( {2,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\ \left( {3,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\ \left( {4,2} \right),\left( {2,4} \right),\left( {4,2} \right) \end{array}\]

Example 6.

Find all paths of length \(2\) in the relation \(S.\)
A binary relation containing paths of length 2.

Solution.

The relation has \(8\) paths of length \(2:\)

\[\begin{array}{l} \left( {1,2} \right),\left( {2,1} \right)\\ \left( {1,2} \right),\left( {2,3} \right)\\ \left( {1,3} \right),\left( {3,2} \right)\\ \left( {2,1} \right),\left( {1,2} \right)\\ \left( {2,1} \right),\left( {1,3} \right)\\ \left( {2,3} \right),\left( {3,2} \right)\\ \left( {3,2} \right),\left( {2,1} \right)\\ \left( {3,2} \right),\left( {2,3} \right) \end{array}\]

Example 7.

Let \(R = \left\{ {\left( {1,2} \right),\left( {2,3} \right),\left( {3,2} \right),\left( {4,1} \right)} \right\}\) be a binary relation on the set \(A = \left\{ {1,2,3,4} \right\}.\) Find the transitive closure of \(R.\)

Solution.

We solve the problem by calculating the connectivity relation \(R^{*}.\) The original relation \(R\) is represented in matrix form as follows:

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

Find the compositions of relations \(R^2,\) \(R^3,\) and \(R^4\) using matrix multiplication:

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

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

\[{{M_{{R^4}}} = {M_{{R^3}}} \times {M_R} }={ \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 0&0&1&0 \end{array}} \right] }\times{ \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&0&\color{red}{1}&0\\ 0&\color{red}{1}&0&0\\ 0&0&\color{red}{1}&0\\ 0&\color{red}{1}&0&0 \end{array}} \right].}\]

We compute the connectivity relation \(R^{*}\) by the formula

\[{R^*} = R \cup {R^2} \cup {R^3} \cup {R^4}.\]

Since \({M_{{R^4}}} = {M_{{R^2}}},\) we can use the simplified expression:

\[{R^*} = R \cup {R^2} \cup {R^3}.\]

This yields:

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

Hence, the transitive closure of \(R\) in roster form is given by

\[{t\left( R \right) = {R^*} }={ \left\{ {\left( {1,2} \right),\left( \color{red}{1,3} \right),\left( \color{red}{2,2} \right),}\right.}\kern0pt{\left.{\left( {2,3} \right),\left( {3,2} \right),}\right.}\kern0pt{\left.{\left( \color{red}{3,3} \right),\left( {4,1} \right),}\right.}\kern0pt{\left.{\left( \color{red}{4,2} \right),\left( \color{red}{4,3} \right)} \right\}.}\]