Find equivalence relations and classes for a given set

Question

Find how many equivalence relations on the set: $\{1,2,3,4,5,6,7\}$ contain the set $\{\langle6,4\rangle,\langle4,7\rangle,\langle3,3\rangle,\langle5,1\rangle\}$

And do not contain the set $\{\langle1,2\rangle,\langle6,1\rangle,\langle2,4\rangle\}$

I know what an equivalence relation is and its properties but I kinda didn't understand the question, and what I should do in order to solve this.

Can someone show me the approach of solving this? Thanks :)

Answer 1

In this answer it is assumed that $\langle1,2\rangle\notin R$, $\langle6,1\rangle\notin R$ and $\langle2,4\rangle\notin R$.

You might have meant that $\{\langle1,2\rangle,\langle6,1\rangle,\langle2,4\rangle\}\nsubseteq R$. Then things are different.

Based on the date we conclude that each of the sets $\{4,6,7\}$ and $\{1,5\}$ must be a subset of an equivalence-class. From $\langle6,1\rangle\notin R$ it follows that these classes are distinct. Element $2$ cannot belong the equivalence class that contains set $\{4,6,7\}$ (since $\langle2,4\rangle\notin R$) neither the class that contains set $\{1,5\}$ (since $\langle1,2\rangle\notin R$). Exactly $4$ possibilities can be discerned:

• $\{2,3\}$, $\{4,6,7\}$ and $\{1,5\}$ are the equivalence classes.
• $\{2\}$, $\{3\}$, $\{4,6,7\}$ and $\{1,5\}$ are the equivalence classes.
• $\{2\}$, $\{3,4,6,7\}$ and $\{1,5\}$ are the equivalence classes.
• $\{2\}$, $\{4,6,7\}$ and $\{1,3,5\}$ are the equivalence classes.

---

Edit:

The relation between the partition of equivalence classes and the equivalence $R$ can be described as follows:

$\langle i,j\rangle\in R\iff i$ and $j$ belong to the same equivalence class.

So if we focus e.g. on the partition secondly mentioned here (the one that you mention in your comment) then we find easily:

$R=\{\langle2,2\rangle,\langle3,3\rangle,\langle4,4\rangle,\langle4,6\rangle,\langle4,7\rangle,\langle6,4\rangle,\langle6,6\rangle,\langle6,7\rangle,\langle7,4\rangle,\langle7,6\rangle,\langle7,7\rangle,\langle1,1\rangle,\langle1,5\rangle,\langle5,1\rangle,\langle5,5\rangle\}$

Answer 2

Well, you start with the relation defined by $R_1 = \{(6, 4), (4, 7), (3, 3), (5, 1)\}$. Then you need to add exactly those pairs to $R_1$, to become $R$, an equivalence relation, with the stipulation that you cannot add any ordered pair in the relation $\{(1, 2), (6, 1), (2, 4)\}$.

Now, if we want our new relation $R$ to be an equivalence relation, it must be reflexive, symmetric, and transitive.

For reflexivity, we must add to $R_1$ the following elements: $(1, 1), (2, 2), (4, 4), (5, 5) (6, 6), (7, 7).$ This gives us $$R_2 = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5) (6, 6), (7, 7), (6, 4), (4, 7),(5, 1)\}$$

For symmetry, we must add to $R_2$, minimally, the elements $(4, 6), (7, 4), (1, 5)$ to give us $$R_3= \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4), (4, 7),(7, 4), (1, 5), (5, 1)\}$$

For transitivity, we must make sure that if $(a, b), (b, c) \in R_3$, then $(a, c) \in R_3$. If any such $(a, c) \notin R_3$, then we need to add them to form our final $R$:

Hence, since $(6, 4) \in R_3$ and $(4, 7) \in R_3$, we need to add $(6, 7)$ to $R_3$, as well as $(7, 6)$ to maintain symmetry.

That gives us $$R = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4), (4, 7),(7, 4), (1, 5), (5, 1), (6, 7), (7, 6)\}$$

Now, we have, minimally, an equivalence relation $R$.

Now you need to determine how many different equivalence relations exist, which must necessarily contain all elements in $R$, but none of the pairs in the set $\{(1, 2), (6, 1), (2, 4)\}$.

For example, you cannot add $(1, 6),$, because that would necessitate, for the sake of maintaining symmetry, adding $(6, 1)$. But you could add $(1, 3), (3, 1)$ to $R$ to form another equivalence relation.