1
$\begingroup$

Let $A={1,2,3}$. How many minimum number of elements must be added to a relation $R$ containing $(1,2)$ and $(2,3)$ so that it becomes an equivalence relation?

My Attempt

We have, $(1,2)$ and $(2,3)$.

Checking for reflexive relation:

$(1,1)$, $(2,2)$ and $(3,3)$ must be added.

Checking for symmetry

$(2,1)$ and $(3,2)$ must be added.

How should I do further?

$\endgroup$
  • 3
    $\begingroup$ Now, you need transitivity. Can you find any pairs of pairs in your list of the form $(a,b)$ and $(b,c)$ - it is important that the two pairs have the same middle element. Then, you can add $(a,c)$. (Then, you use symmetry to add $(c,a)$.) $\endgroup$ – Michael Burr Mar 30 '17 at 11:17
  • $\begingroup$ @MichaelBurr, what is mean by transitivity? $\endgroup$ – pi-π Mar 30 '17 at 11:23
  • $\begingroup$ For an equivalence relation to exist, it needs to be transitive too. See this en.wikipedia.org/wiki/Transitive_relation?wprov=sfla1 $\endgroup$ – Jaideep Khare Mar 30 '17 at 11:28
3
$\begingroup$

An equivalence relation on $A$ has three properties: reflexivity, symmetry, and transitivity.

Reflexivity means that: "For all $a\in A$, $(a,a)\in R$." You have successfully added the pairs to make the relation reflexive by adding $(1,1)$, $(2,2)$, and $(3,3)$.

Symmetry means that: "If $(a,b)\in R$, then $(b,a)\in R$." You have successfully added the pairs (thus far) to make the relation symmetric by adding $(2,1)$ since $(1,2)$ is in the relation and $(3,2)$ since $(2,3)$ is in the relation.

Transitivity means that: "If $(a,b),(b,c)\in R$, then $(a,c)\in R$." You have not dealt with transitivity in your argument. In particular, there are pairs that you have in your relation of the form $(a,b)$ and $(b,c)$, but $(a,c)$ hasn't been added to the relation.

I teach these relations using dominos. In particular, for reflexivity, you've always got to have the dominos that have the same value on both sides. For symmetry, you're allowed to spin the dominos so that the left becomes the right. For transitivity, you're allowed to put two dominos together if they have the same value on one side (technically, this last description uses both symmetry and transitivity).

I don't want to give a partial answer because any partial answer is actually a full answer.

$\endgroup$
  • $\begingroup$ what is minimum number of elements to be added? $\endgroup$ – pi-π Mar 30 '17 at 11:46
  • $\begingroup$ Two are given. You've listed $5$ that you need to add, but I am hinting that you are not done. There are at maximum $7$ that you could possibly add, so you have to use transitivity to figure out if you need to add one or two more elements. $\endgroup$ – Michael Burr Mar 30 '17 at 12:20
1
$\begingroup$

Only transitivity pending.

Transitive -

Let $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R$ should be there.

So far we have,

$R = {(1,2),(2,3),(1,1),(2,2),(3,3),(2,1),(3,2)}$

Now $(1,2),(2,3)$ there so we need $(1,3)$

Hope you can proceed further now.

$\endgroup$
0
$\begingroup$

If you think of the relation as a graph, then you are looking for semi-connected components (connected by lines without arrows). The transitive closure is the union of the complete subgraph of each such component. Since

  • 1 is connected to 2 and
  • 2 is connected to 3 ...

1, 2, and 3 are in the same component, which has $n^2$ arcs in its complete (sub)graph, where $n$ is the number of nodes. ...

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