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
  • 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, 2017 at 11:17
  • $\begingroup$ @MichaelBurr, what is mean by transitivity? $\endgroup$
    – pi-π
    Mar 30, 2017 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, 2017 at 11:28

3 Answers 3

Reset to default
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$
2
  • $\begingroup$ what is minimum number of elements to be added? $\endgroup$
    – pi-π
    Mar 30, 2017 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, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .