Relations of equivalence...

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$



Answers 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}

GNU Supporter
GNU Supporter
January 14, 2018 13:19 PM

Related Questions


Understanding Equivalence Classes?

Updated August 25, 2017 21:20 PM

Union of equivalence classes

Updated November 11, 2017 01:20 AM