Given is relation $R$. Create a digraph for equivalence relation

1.2k Views Asked by At

Given is relation $R = \left\{(1,1),(1,5),(2,4),(3,3),(4,1),(4,2),(5,4)\right\}$

What's its equivalence relation $h_{\text{equiv}}(R)$? Draw a digraph for $h_{\text{equiv}}(R)$.

I check in internet a relation is equivalence relation if it have properties: reflexive, symmetric, transitive.

This means I need change relation $R$ so it have these $3$ properties, right?

Is allowed when I only take $\left\{(1,1)\right\}?$

Because this is reflexive because we only have $1$ and it's relation with $1$, it's symmetric too and also transitive because transitivity need two condition satisfied and this we have only one pair so we don't need second condition of transitivity satisfied. So also transitive relation.

We have $h_{\text{equiv}}(R) = \left\{(1,1)\right\}$

Digraph:

enter image description here

1

There are 1 best solutions below

0
On BEST ANSWER

Given your description of $$R = \{ (1,1), (1,5), (2,4), (3,3), (4,1), (5,4) \},$$ I suppose this is a relation on the set $$\{ 1, 2, 3, 4, 5 \}.$$ If $h_{equiv}(R)$ is the equivalence relation generated by $R$, then you can obtain this relation by following the procedure:

  1. It must be reflexive, so you must add it the pairs $(2,2), (4,4), (5,5)$.
  2. It must be symmetric, so from the existence of pairs $(1,5), (2,4), (4,1), (5,4)$, you also need $(5,1), (4,2), (1,4), (4,5)$.
  3. It must be transitive, so given that $(1,4), (4,2) \in h_{equiv}(R)$ it follows that $(1,2) \in h_{equiv}(R)$ (and also $(2,1)$); from $(5,4), (4,2) \in h_{equiv}(R)$ it follows that $(5,2) \in h_{equiv}(R)$ (and $(2,5)$ too).

So \begin{align} h_{equiv}(R) &= \{ (1,1), (1,2), (1,4), (1,5), (2,1), (2,2), (2,4), (2,5), \\ &(3,3), (4,1), (4,2), (4,4), (4,5), (5,1), (5,2), (5,4), (5,5) \} \end{align}

Its graph is the complete graph on the set $\{1,2,4,5\}$ union with the single element $\{3\}$