Answer to Question #284169 in Discrete Mathematics for Aarush

Question

For the relation R = {(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)}

1.Using warshall algorithm find the transitive closure R* of R

2.write matrix representation of R*

3.Check whether the relation of R* is an equivalence relation or a partial order.

Answer 1

Consider a relation $R = \{(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)\}$ on the set $A=\{p,q,r,s,m\}$.

1. Let us state the steps of the Warshall's algorithm:

1. Let $W:=M_R,\ k:=0.$

2. Put $k:=k+1.$

3. For all $i\ne k$ such that $w_{ik}=1$ and for all $j$ let $w_{ij}=w_{ij}\lor w_{kj}.$

4. If $k=n$ then stop and $W=M_{R^*},$ else go to step 2.

Let us find transitive closure of the relation $R$ using Warshall's algorithm:

$W^{(0)}=M_R =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

$W^{(1)} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

$W^{(2)} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

$W^{(3)} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

$W^{(4)} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

$M_{R^*}=W^{(5)} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

It follows that $R^*= \{(p,p) ,(q,p),(q,q),(r,r),(r,s), (r,m),(s,s) ,(s,m) ,(m,m)\}.$

2. Let us write the matrix representation of $R^*.$ It follows from the previous item that

$M_{R^*} =\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$

3. Let us check whether the relation of $R^*$ is an equivalence relation.

Since $(q,p)\in R^*$ but $(p,q)\notin R^*,$ we conclude that the relation is not symmetric, and hence it is not an equivalence relation.

Let us check whether the relation of $R^*$ is a partial order.

Since $\{(p,p),(q,q),(r,r),(s,s) ,(m,m)\}\subset R^*,$ the relation $R^*$ is reflexive. Taking into account that $(a,b)\in R^*$ and $(b,a)\in R^*$ imply $a=b$ for any $(a,b),(a,b)\in R^*$, we conclude that this relation is antisymmetric. Since $R^*$ is the transitive closure, it is transitive.

We conclude that $R^*$ is a partial order.