2
$\begingroup$

Given the set $A=\{1,2,3,4,5,6\}$ how many equivalence relations ( symmetric, reflexive and transitive ) can you form if the following pairs are disallowed: $\{ (3,4),(2,4),(2,3),(1,4),(1,3),(1,2)\}$ ? All six must not be present.

I saw this on a final exam and had no idea how to even approach it.

  • 0
    Do you know that an equivalence relation splits a set into separate classes? Since your constraints all involve 1-4, I would suggest working out how they could be split into classes to comply with the constraints, and then working out the possibilities for 5 and 6. It is a question of organising the information as much as anything else.2012-04-03
  • 0
    @MarkBennet Yes, but I wasn't sure how to apply that to the problem.2012-04-03
  • 0
    I think joriki has implemented my suggestion in his answer (which was independently constructed, as it was posted just as I posted my comment).2012-04-03

2 Answers 2