Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Mark Bennet Apr 3 '12 at 8:52
    
@MarkBennet Yes, but I wasn't sure how to apply that to the problem. –  Robert S. Barnes Apr 3 '12 at 9:06
    
I think joriki has implemented my suggestion in his answer (which was independently constructed, as it was posted just as I posted my comment). –  Mark Bennet Apr 3 '12 at 11:18

2 Answers 2

First of all, note that if $(3,4)$ is disallowed, by symmetry, $(4,3)$ is disallowed as well. By building the symmetric closure of the forbidden set, we find that the following pairs are disallowed: $(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4)$.

Next, by reflexivity, every equivalence relation must contain $(a,a)$ for $a = 1,\ldots, 6$.

Furthermore, if $(1,5)$ and $(5,2)$ were part of the relation, then by transitivity, $(1,2)$ would be part as well, which is impossible. Thus, there are at most one $a$ and one $b$ such that $(a,5)$ and $(b,6)$ (as well as $(5,a)$ and $(6,b)$ by symmetry) are part of the relation.

If $(5,6)$ is part of the relation, we cannot have $(a,5)$ and $(b,6)$ in the relation for $1 \le a,b\le 4$, $a \neq b$ by another transitivity argument.

Therefore, there are two classes of equivalence relations: Those containing $(5,6)$ and those not containing $(5,6)$.

With further symmetry and transitivity arguments we find that if $(a,5)$ and $(5,6)$ are in the relation, so is $(a,6)$ (and all their symmetric forms), and vice-versa. Therefore, there are four equivalence relations with $(5,6)$ and $(a,5)$ for $1 \le a \le 4$. Add the case where none of these pairs is added, and you find there are exactly 5 cases with $(5,6)$.

In the case that $(5,6)$ is not in the set, one finds that there are three main sub-classes: The identity relation (one member), sets that contain $(a,5)$ (four members), sets that contain $(a,6)$ (four members) and sets that contain $(a,5)$ and $(b,6)$ for $a\neq b$ ($4 \cdot 3 = 12$ members). All in all, there are 26 different equivalence relations.

share|improve this answer
    
+1 for all the details –  draks ... Apr 3 '12 at 9:06

The disallowed pairs are all pairs of numbers $1$ through $4$. Thus these four must be in equivalence classes of their own, and the only remaining options are where to put $5$ and $6$. We can add each of them either to one of the four classes containing $1$ to $4$ or to a further class. That gives $5^2=25$ possibilities, and then there's the further possibility of having them both in classes of their own, for a total of $26$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.