Relation Properties C9Ca8C

1. **Problem Statement:** We are given two relations $R$ on sets $A$ and asked to analyze properties, construct matrix representations, and compute degrees and transitive closures. --- ### Part a) 2. **Given:** $A = \{1, 2, 3, 5, 7\}$ $R = \{(1, 1), (2, 2), (2, 3), (3, 5), (5, 3), (5, 7), (7, 2), (7, 3), (7, 7)\}$ 3. **(i) Domain and Range:** - Domain is the set of all first elements in ordered pairs of $R$. - Range is the set of all second elements in ordered pairs of $R$. Domain $= \{1, 2, 3, 5, 7\}$ Range $= \{1, 2, 3, 5, 7\}$ 4. **(ii) Matrix Representation:** The matrix $M$ is a $5 \times 5$ matrix where rows and columns correspond to elements $1, 2, 3, 5, 7$ in that order. Fill $M[i,j] = 1$ if $(i,j) \in R$, else $0$. $$ M = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 \end{bmatrix} $$ 5. **(iii) In-degree and Out-degree:** - Out-degree of vertex $v$ is the number of edges going out from $v$. - In-degree of vertex $v$ is the number of edges coming into $v$. Calculate for each vertex: - Vertex 1: Out-degree = 1 (to 1), In-degree = 1 (from 1) - Vertex 2: Out-degree = 2 (to 2,3), In-degree = 1 (from 7) - Vertex 3: Out-degree = 1 (to 5), In-degree = 2 (from 2,5,7) actually 3 edges from 2,5,7 - Vertex 5: Out-degree = 2 (to 3,7), In-degree = 1 (from 3) - Vertex 7: Out-degree = 3 (to 2,3,7), In-degree = 1 (from 5) Correcting counts: - Vertex 1: Out-degree = 1, In-degree = 1 - Vertex 2: Out-degree = 2, In-degree = 1 - Vertex 3: Out-degree = 1, In-degree = 3 - Vertex 5: Out-degree = 2, In-degree = 1 - Vertex 7: Out-degree = 3, In-degree = 1 --- ### Part b) 6. **Given:** $A = \{1, 2, 3, 4\}$ $M_R = \begin{bmatrix}1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1\end{bmatrix}$ 7. **(i) Properties:** - **Reflexive:** Check diagonal entries. Diagonal is $(1,0,0,1)$ so not all 1s. So, not reflexive. - **Irreflexive:** No diagonal entries should be 1. Here some are 1, so not irreflexive. - **Symmetric:** Check if $M[i,j] = M[j,i]$ for all $i,j$. For example, $M[1,4] = 1$ but $M[4,1] = 1$ (okay), $M[2,1] = 1$ and $M[1,2] = 0$ (not equal), so not symmetric. - **Antisymmetric:** If $M[i,j] = 1$ and $M[j,i] = 1$ then $i = j$. Check pairs: $M[1,4] = 1$ and $M[4,1] = 1$ but $1 \neq 4$, so not antisymmetric. - **Asymmetric:** Must be antisymmetric and irreflexive. Not irreflexive, so no. - **Transitive:** Check if whenever $M[i,j] = 1$ and $M[j,k] = 1$, then $M[i,k] = 1$. Counterexample: $M[2,1] = 1$ and $M[1,4] = 1$ but $M[2,4] = 0$, so not transitive. 8. **(ii) Equivalence Relation:** - Equivalence requires reflexive, symmetric, and transitive. - Since $R$ is not reflexive, symmetric, or transitive, $R$ is not an equivalence relation. 9. **(iii) Warshall’s Algorithm:** - Initialize $W^{(0)} = M_R$. - For $k = 1$ to $4$, update $W^{(k)}[i,j] = W^{(k-1)}[i,j] \lor (W^{(k-1)}[i,k] \land W^{(k-1)}[k,j])$. - After applying Warshall’s algorithm, the transitive closure matrix is: $$ \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} $$ --- **Final answers:** - a(i) Domain = $\{1,2,3,5,7\}$, Range = $\{1,2,3,5,7\}$ - a(ii) Matrix $M$ as above - a(iii) In-degree and Out-degree as above - b(i) $R$ is neither reflexive, irreflexive, symmetric, antisymmetric, asymmetric, nor transitive. - b(ii) $R$ is not an equivalence relation. - b(iii) Transitive closure matrix as above.