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 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 P contains R such that

then R+ is a closure of R with respect to property 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^+,\;r\left( R \right),\;cl_{ref}\left( R \right),\;refc\left( R \right),\text{ etc.}\]

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

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

Respectively, the transitive closure is denoted by

\[{R^t},\;{R_t},\;R_t^+,\;t\left( R \right),\;cl_{trn}\left( R \right),\;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.\) \(\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)},\left( {2,4} \right),{\left( {3,3} \right)},\left( {4,2} \right),{\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),\left( {2,4} \right),\left( {4,3} \right)} \right\} \cup \left\{ {\left( \color{red}{2,1} \right),\left( \color{red}{3,1} \right),\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),\left( {2,2} \right),\left( {2,4} \right),\left( \color{red}{3,1} \right),\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],\;\;{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 ,\left( {{x_{n - 1}},b} \right),\]

in the relation \(R,\) where \(n\) is a 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 } \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),\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).\)

See solved problems on Page 2.

Page 1 Page 2