by Jon D
Last Updated January 14, 2018 13:20 PM

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$

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

- $|A/{\cal R}| = 3$: there are three partitions
- $1 {\cal R} 2$: $1$ and $2$ are in the same partition
- $ [2]_{\cal R} \ne [3]_{\cal R}$: $2$ and $3$ are in different partitions
- $[4]_{\cal R} = [5]_{\cal R}$: $4$ and $5$ are in the same partition
- $|[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}

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger