0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ No, you are required to add as few as possible pairs to R to make it zn equivalence relation. $\endgroup$ – William Elliot Nov 12 '17 at 11:44
1
$\begingroup$

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\}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.