Proving The existence of Set Y from non-empty Set X with an equivalence relation defined on X.

Question

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?

Answer 1

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).