Question

To determine the transitive closures of these relations on \(\{ 1,2,3,4\} \).

Short answer

The matrix formed is \(\left( {\begin{array}{*{20}{l}}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1\end{array}} \right)\).

Step-by-step solution

Given data

Given data \(R = \{ (1,1),(1,4),(2,1),(2,3),(3,1),(3,2),(3,4),(4,2)\} \)

\(A = \{ 1,2,3,4\} \).

Concept used of transitive closure property

The transitive closure of\(R\)is defined as the smallest transitive relation of\(R\).

Represent relation \(R\) by matrix

A relation\(R\)can be represented by the matrix\({M_R} = \left( {{m_{ij}}} \right)\)

\({m_{ij}} = \left\{ {\begin{array}{*{20}{l}}{1{\rm{ if }}\left( {{a_i},{b_j}} \right) \in R}\\{0{\rm{ if }}\left( {{a_i},{b_j}} \right) \notin R}\end{array}} \right.\)

The composite \(S^\circ R\) consists of all ordered pairs \((a,c)\) for which there exists an element b such that \((a,b) \in R\) and \((b,c) \in S\).

Simplify for closure

Algorithm 1 finds the transitive closure by computing the successive powers and taking their join. We exhibit our answers in matrix form as \({M_R} \vee M_R^{|2|} \vee \ldots \vee M_R^{(n)} = {M_R}\)

\(\left( {\begin{array}{*{20}{l}}1&0&0&1\\1&0&1&0\\1&1&0&1\\0&1&0&0\end{array}} \right) \vee \left( {\begin{array}{*{20}{l}}1&1&0&1\\1&1&0&1\\1&1&1&1\\1&0&1&0\end{array}} \right) \vee \left( {\begin{array}{*{20}{l}}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&0&1\end{array}} \right) \vee \left( {\begin{array}{*{20}{l}}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1\end{array}} \right)\)

\( = \left( {\begin{array}{*{20}{l}}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1\end{array}} \right)\).