Minimum Equivalence Relation

Question

Let $X= \{1,2,3,4\}$, and $R = \{(1,2),(3,4)\}$. Show the minimum equivalence relation on $X$ that extends $R$. How many elements does the quotient set $X/R$ have ? Can somebody give hints to solve it ?

Answer 1

Since $R$ is already transitive, it suffices to take the reflexive and symmetric closure of $R$. To make $R$ reflexive, union it with the identity relation: $$ \{(a,a) \mid a \in X\} $$

To make $R$ symmetric, union it with its opposite ordered pairs: $$ \{(a,b) \mid (b,a) \in R \} $$

Can you take it from here? Spoiler below:

This yields the new equivalence relation: $$R^* = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\}$$ which partitions $X$ into the following $2$ equivalence classes: $$\{1,2\} \qquad\text{and}\qquad \{3,4\}$$ Thus, the quotient set $X/R^*$ has $2$ elements.

Answer 2

HINT: By definition an equivalence relation is reflexive, so if $E$ is the minimum equivalence relation on $X$ extending $R$, then $E$ must contain the pairs $\langle 1,1\rangle,\langle 2,2\rangle,\langle 3,3\rangle$, and $\langle 4,4\rangle$. It is also symmetric, so since it contains $\langle 1,2\rangle$, it must contain the pair $\langle 2,1\rangle$ as well. What other pair must it contain in order to be symmetric? Let $S$ be the relation that you get when you make all of these additions to $R$.

Finally, $E$ must be transitive. That is, if $x,y,z\in X$, $\langle x,y\rangle\in E$, and $\langle y,z\rangle\in E$, then $\langle x,z\rangle$ must be in $E$. Do you need to add anything to $S$ to make it transitive, or does it already have this property?

It isn’t the quotient $X/R$ that you want: it’s $X/E$. This is just the set of equivalence classes of the equivalence relation $E$. If you understand what an equivalence class is, you should have no trouble determining how many there are, but here’s a start: what elements of $X$ are related to $1$ by $E$? The set of all of those is one of the equivalence classes.