Proving The existence of Set Y from non-empty Set X with an equivalence relation defined on X. Let $X$ be a nonempty set and let $\sim$ be an equivalence relation defined on $X$.
Prove that there exist a set $Y$ and a function $f \colon X \to Y$, such that for all $a, b \in X$:
$$a \sim b \iff f(a) = f(b).$$
How do I go about this?
 A: For every $x\in X$, let $[x] = \{a \in X \mid x \sim a\}$ be the equivalence class of $x$ generated by $\sim$, i.e. the set of elements of $X$ that are equivalent (by $\sim$) to $x$.
Let $Y = X{/{\sim}} = \{[x] \mid x \in X\}$, i.e. $Y$ is the quotient set of $X$ by $\sim$.
Let $f\colon X \to Y$ be the function such that $f(x) = [x]$ for every $x\in X$.
It is easy to prove that, for every $a, b \in X$, $a \sim b$ if and only if $f(a) = f(b)$. Indeed:


*

*if $a \sim b$ then $[a] = [b]$ and hence $f(a) = f(b)$;

*if $f(a) = f(b)$ then $[a] = [b]$ and hence $a \sim b$.



Aside remark (inessential to answer the question). In my opinion, the hypothesis that $X$ is nonempty is superfluous. Indeed, if $X = \emptyset$ then necessarily $\sim$ is the empty relation, which is an equivalence relation. In this case, the quotient set is $Y = X / {\sim} = \{\emptyset\}$, because there is only one (empty) equivalence class.
Therefore, the empty function $f \colon X \to Y$ vacuously satisfies that for every $a, b \in X$, $a \sim b$ if and only if $f(a) = f(b)$ (since $X$ is empty).
