# Number of Equivalence Relations over $A$ with Restrictions

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.

-
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

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$.

-

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.

-
+1 for all the details –  draks ... Apr 3 '12 at 9:06