Relations of equivalence...

Question

Given the set $A = \{1,2,3,4,5,6,7\}$.

How can I establish how many and what are the equivalence relations $R$ on $A$ that meet all the following conditions?

1) $|A/R| = 3$

2) $1 R 2$

3) $[2]_R\neq[3]_R$

4) $[4]_R = [5]_R$

5) $|[7]_R| = 3$

Answer 1

Since partition and equivalence relation are equivalent, it suffices to consider the ways to partition $A$.

1. $|A/{\cal R}| = 3$: there are three partitions
2. $1 {\cal R} 2$: $1$ and $2$ are in the same partition
3. $ [2]_{\cal R} \ne [3]_{\cal R}$: $2$ and $3$ are in different partitions
4. $[4]_{\cal R} = [5]_{\cal R}$: $4$ and $5$ are in the same partition
5. $|[7]_{\cal R}|=3$: partition $[7]_{\cal R}$ has three elements.

We start with $\{\{1,2\},\{3\},\{\}\}$.

• $[4]_{\cal R} = [1]_{\cal R}$
  This gives $\{\{1,2,4,5\},\{3\},\{\}\}$. Wherever we put $7$, property (5) is violated.
• $[4]_{\cal R} = [3]_{\cal R}$
  From $\{\{1,2\},\{3,4,5\},\{\}\}$ and property (5), the only choice is $\{\{1,2,7\},\{3,4,5\},\{6\}\}$.
• Otherwise, $\{\{1,2\},\{3\},\{4,5\}\}$. Use property (5) again.
  • When $7$ is in the first or the third partition, $6$ can be in either of the other two partitions.
  • When $7$ is in the second partition, then so as $6$.

We have $1+2\times2+1=6$ choices. \begin{align} & \{\{1,2,7\},\{3,4,5\},\{6\}\} \\ & \{\{1,2,7\},\{3,6\},\{4,5\}\} \\ & \{\{1,2,7\},\{3\},\{4,5,6\}\} \\ & \{\{1,2\},\{3,6,7\},\{4,5\}\} \\ & \{\{1,2,6\},\{3\},\{4,5,7\}\} \\ & \{\{1,2\},\{3,6\},\{4,5,7\}\} \\ \end{align}