Proving a bijective correspondence between a set of equivalence classes $A^*$ and a set $B$

Question

Let $f : A \to B$ be a surjective function. Let us define a relation on $A$ by setting $a_0$ ~ $a_1$ if $f(a_0) = f(a_1)$. This relation is an equivalence relation. Let $A^*$ be the set of equivalence classes. Show that there is a bijective correspondence of $A^*$ with $B$

Now if $E$ is an equivalence class, then $E = A^*$, as two equivalence classes are either equal or disjoint. So $A^* = \{a_i :a_i$ ~ $a_j \} = \{a_i : f(a_i) = f(a_j)\}$

I need to prove that $f$ needs to be both surjective and injective to prove a bijective correspondence between $A^*$ and $B$. But I'm not sure how to go about doing so, in this specific case, Any hints would be appreciated.

Answer 1

Hint: You can define a new function $\overline{f}: A^* \to B$ by $$\overline{f}([a]) = f(a)$$

I claim that $\overline{f}$ is a bijection. To prove this, you'll need to show that:

1. $\overline{f}$ is a well-defined function (does it depend on how we represented the class $[a]$?)
2. $\overline{f}$ is injective
3. $\overline{f}$ is surjective

Answer 2

Let $A^*=\{A_i\}$ the set of equivalence classes for $f$. We define a map $\bar f\colon A^*\longrightarrow B$ by $\;\bar f (A_i)=f(\text{any}\enspace x\in A_i)$.

This map is well defined by construction, since all elements in an equivalence class have the same image.

It is injective, for if $\bar f(A_i)=\bar f(A_j)$, for any elements $x\in A_i$ and $y\in A_j$, we have $f(x)=f(y)$. This means $x\sim y$, hence $A_i=A_j$.

Finall, if we denote $\pi\colon A\longrightarrow A^*$ the canonical map $x\longmapsto [x]$, we have, by construction, $\;f=\bar f\circ \pi$. It is well known that if the composition of two maps is surjective, the second (in order of composition) is surjective. Hence $\bar f$ surjective.