Smallest pairs to be added to a set to make it an equivalence relation

Question

$$R = \{(1,1), (1,3), (1,5), (4,4),(4,6)\}, \quad A = \{1,2,3,4,5,6\}$$

Determine the smallest set of pairs of elements which needs to be added to $R$ so that the resulting relation $\Bbb{R}^*$ is an equivalance relation.

My atttempt:

In order for it to equivalent relation it needs to be reflective, symmetric and transitive.

This would mean that the lowest reflective pair is $(1,1)$ which is already in $\Bbb{R}$.

There seem to be no transitive pairs within $\Bbb{R}$ and no symmetric pairs either.

Question: I am wondering how would this solved as I assumed you would write out all the other pairs that are not in $\Bbb{R}$ which would make up $\Bbb{R}^*$.

Answer 1

Hint: Think about this in terms of equivalence classes, rather than an equivalence relation: what is the most fine-grained partition of $A$ into equivalence classes that $R$ "allows"?

For instance, letting $A$ have only one equivalence class would be allowed by $R$, but it's probably not the most fine-grained. On the other hand, letting each element be alone in its own equivalence class is the most fine-grained you can get, but it is not allowed by $R$. You need to find the middle gound here.

Once you have the equivalence classes, you can find the corresponding equivalence relation, and figure out which pairs are in there.

Answer 2

This would mean that the lowest reflective pair is $(1,1)$ which is already in R.

You need to add the least amount of pairs needed to make $R^\ast$ reflexive.   Merely having $(1,1)$ will not make $R^\ast$ reflexive, on its own.   Some new pairs will need to be added.

To be reflexive will require that $\forall x\in A: (x,x)\in R^\ast$, what is, for every element $x$ in $\{1,2,3,4,5,6\}$ the pair $(x,x)$ needs to be in $R^\ast$.   So what pairs need to be added to make this so?

There seem to be no transitive pairs within $R$ and no symmetric pairs either.

Indeed, that is why they need to be added.   Your task is to add the fewest necessary pairs to make $R^\ast$ transitive and symmetric.   (PS: remember the pairs added above will still be needed to be in $R^\ast$.)

Start with symmetry.