[Math] 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

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.