If $f$ surjects from $A$ to $B$ then there is a bijection $\phi$ from a subset of $A$ to $B$ Let $A$ be a set and let $ f: A \to B $ be a surjective function. Prove that there exists a subset $ C \subseteq A $ and a function $ \phi: C \to B $ such that $ \phi $ is bijective.
I did it by giving particular examples, giving $ A = \{1,2,3 \} $ and $ B = \{1,2 \} $ and the function $f(x)=\begin{cases}
 1& \text{ if } x=1 \\ 
 1& \text{ if } x=2 \\ 
 2& \text{ if } x=3 
\end{cases}$ it is clearly a surjective function. Now if $ C = A \setminus \{1 \} $ what is desired remains. Guiding me from particular examples, I thought to consider the set $ C $ of all the images that are repeated because the function is not necessarily injective, as in the previous example removing 1, since it repeated with 2. But I don't know if the idea is well and I don't know how to express that set either. I tried as follows, $ C = A\setminus \{f (a) = f (b) \wedge a \neq b \mid \forall a, b \in A \} $ but I don't know if it's ok. Help.
 A: You can’t actually prove it by giving examples; the best that you can do is illustrate the concept that you have in mind. You’ve already recognized that what you have to worry about are the elements $b\in B$ such that the set $\{a\in A:f(a)=b\}$ has more than one element. What if for each $b\in B$ you let $A_b=\{a\in A:f(a)=b\}$? You know that each of these sets is non-empty; why? Thus, from each of them you can single out an element $a_b$. (Of course when $A_b$ has only one element, that element will automatically be $a_b$. In the absence of any other information about $A$ there is no way to specify how the others are chosen.) Now use these elements $a_b$ to define a suitable $C$.
Added: I should probably mention that in general choosing the elements $a_b$ requires the axiom of choice, though in specific cases it may not be necessary.
A: Let's define in $A$ the equivalence relation $a\sim a' \stackrel{(def.)}{\iff} f(a)=f(a')$.
Claim.
The map $\psi_f\colon (A/\sim)\to B$, defined by $\psi_f([a]_\sim):=f(a)$, is well-defined and bijective.
Proof.

*

*Good definition: $a'\in [a]_\sim \Rightarrow [a']_\sim= [a]_\sim \Rightarrow\psi_f([a']_\sim)=\psi_f([a]_\sim)=f(a)$;

*Surjectivity: by the surjectivity of $f$ and the definition of $\psi_f$, $\forall b\in B, \exists a\in A\mid b=f(a)=\psi_f([a]_\sim)$;

*Injectivity: $\psi_f([a]_\sim)=\psi_f([a']_\sim)\Rightarrow f(a)=f(a')\Rightarrow a\sim a'\Rightarrow [a]_\sim=[a']_\sim\space$.

$\Box$
Moreover, by the Axiom of Choice, there is a bijection $\varphi\colon (A/\sim)\to R$, where $R\subseteq A$ is a set of representatives (see e.g. here). Therefore, your sought bijection is $\phi\colon R\space(\subseteq A)\to B$ defined by $\phi:=\psi_f\circ \varphi^{-1}$:
$\color{white}{............................}$ 
