I'm having trouble trying to understand the smallest equivalence relation containing a specific subset.

Q: Find the smallest equivalence relation $R$ on $M = \{1,2,3,4,5\}$ which contains the subset $R_0 = \{(1,1), (1,2), (2,4), (3,5)\}$

I know this is probably really simple but I just cant get it. Is anyone able to explain this to me? I've tried to find explanations elsewhere, but nothing I can find talks about the smallest equivalence relation.

From Comments:

Adding (2,2), (3,3), (4,4), (5,5) makes it Reflexive

Adding (2,1), (4,2), (5,3) makes it Symmetric

Adding (1,4), (4,1) makes it Transitive

So the smallest equivalence relation would be the R0 + those added?

  • $\begingroup$ First, is $R_0$ an equivalence relation? If not, can you think of elements that you could add to $R_0$ to make it an equivalence relation? Once you can do that, you can then start to think about how to do this ``minimally". $\endgroup$ – Matthew Conroy Aug 31 '16 at 0:54
  • $\begingroup$ @MatthewConroy Check the edit, is that right? $\endgroup$ – NuMs Aug 31 '16 at 1:42
  • $\begingroup$ Yes. Your edit contains the correct solution. $\endgroup$ – Browning Aug 31 '16 at 2:36

Your Answer

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

Browse other questions tagged or ask your own question.