Transitive Closure

The closure of a binary relation R on a set A, with respect to a property (reflexivity, symmetry, transitivity) is a relation which meets the following three criteria.

1. The relation contains R.
2. The relation possesses the property.
3. The relation has the fewest number of ordered pairs that satisfies both criteria listed above.

The reflexive closure of R is given by \( R \cup \left \{(x,x): x \epsilon A\right \}\).
The symmetric closure of R is given by \( R \cup \left \{(y,x): (x,y) \epsilon A\right \}\).


Finding transitive closure is not as simple. Consider the relation \(R = \left \{(1,2), (3,1), (1,4), (4,3)\right \}\). We may be tempted to think that the transitive closure is given by \(R \left \{(3,2), (3,4), (1,3), (4,1)\right \}\). This new relation satisfies property 1 above but does it satisfy 2? No, it is missing (1,1), (3,3) and so on.

One method to find the transitive closure is to use Warshall's algorithm. Given a relation R on set A (which has n members), Warshall's algorithm takes as input the n x n 0-1 matrix representing R,  \(M_{R}\), and outputs a matrix representing the transitive closure of R,  \(M_{R^{*}}\).

Warshall's Algorithm:

\(for \ k = 1\  to\  n\)
    \(for\  i = 1\  to\  n\)
        \(for\  j = 1\  to\  n\)
            \(w_{ij} = w_{ij} \vee (w_{ik} \wedge w_{kj})\)

Examining the innermost loop we note that only j (which represents our columns in our matrix) is changing. The counters i and k remain constant. 

If \(w_{ik}\) is 0 then the row remains unchanged since  \(w_{ik} \wedge w_{kj}\) evaluates to 0.

If \(w_{ik}\) is 1 then \(w_{ij}\) takes the value of \(w_{ij} \vee w_{kj}\). If \(w_{ij}\) is 1 it stays as 1. If \(w_{kj}\) is 1 then \(w_{ij}\) is updated to 1. In other words we replace the \(i^{th}\) row with the result of boolean addition of the \(i^{th}\) and \(k^{th}\) rows.

Let's look at an example. Let's find the transitive closure of R={(1,1), (1,3), (2,1), (3,2)} using Warshall's algorithm.

\(M_{R} =\begin{bmatrix} 1  &0 &1 \\1  &0 &0 \\ 0  &1 &0\end{bmatrix}\)

\(k = 1: W_{1} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 0  &1 &0\end{bmatrix}\)

\(k = 2: W_{2} = \begin{bmatrix} 1  &0 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

\(k = 3: W_{3} = \begin{bmatrix} 1  &1 &1 \\1  &0 &1 \\ 1  &1 &1\end{bmatrix}\)

So, \(M_{R^{*}}\) = {(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), (3,3)}