If all mappings $f: A\to B$ are many-to-one, does there exist surjective $g: A\to B$? Suppose sets $A$ and $B$ [edit: for $B\ne \emptyset$] are such that all mappings $f: A\to B$ are many-to-one (i.e. not injective). Can we prove that there must exist a surjective $g: A\to B$? Ideally, I am hoping to be able to construct $g$.
 A: Using the axiom of choice, you can show that $|A| \leq |B|$ or $|B| \leq |A|$. (Each of the two sets are in bijection to a certain ordinal, say $\alpha$ and $\beta$, because they can be well-ordered. Then $\alpha \leq \beta$ or $\beta \leq \alpha$). Hence, there is an injection of $A$ into $B$ or of $B$ into $A$.
Your assumption excludes the first case. Hence, there is an injection $f : B \to A$. Now any left inverse of $f$ will be a surjection $g : A \to B$.
A: If the axiom of choice holds, then the trichotomy principle holds. Namely either $|A|\leq|B|$ in which case there is an injection from $A$ into $B$ and the assumption fails, or $|B|<|A|$ in which case there is an injection from $B$ into $A$, and therefore a surjection from $A$ onto $B$.
Without the axiom of choice it is possible that there is no injection from $A$ into $B$, and there is no surjection from $A$ onto $B$ either. So there's little hope in constructively exhibiting a surjection.
If this happens for any two non-empty $A,B$ then the axiom of choice holds, since taking $A$ to be the least ordinal $\alpha$ such that there is no injection from $\alpha$ into $B$, we have that there is no injection from $A$ into $B$ and therefore there is a surjection from $A$ onto $B$, so $B$ can be well-ordered.

Using "just" the axiom of choice seems asking a bit too much, since we do have to utilize some mechanism to ensure that we can stitch the functions together. We can use transfinite recursion for that.
Choose some function $f_0$ from $A$ into $B$. Suppose $f_\alpha$ was chosen since it's not injective there is some $a_0,a_1$ which are mapped to the same element. If $f_0$ is surjective then we're done; otherwise choose some $b_1$ not in its range, and let $f_{\alpha+1}$ be $f_\alpha\setminus\{(a_1,f_\alpha(a_1))\}\cup\{(a_1,b_1)\}$. Then $f_{\alpha+1}$ is a function from $A$ to $B$, therefore not injective, and the process must continue.
If $\alpha$ is a limit ordinal and $f_\beta$ were defined for all $\beta<\alpha$, then for each $b\in\bigcup\operatorname{rng}(f_\beta)$ we choose some $a$ such that $f_\beta(a)=b$ and $\beta$ is the least ordinal such that $b\in\operatorname{rng}(f_\beta)$, and we define $f_\alpha(a)=b$. Then $f_\alpha\neq f_\beta$ for all $\beta<\alpha$, since the range of $f_\alpha$ is equal to the above union, which is different from the range of any $f_\beta$ (since the ranges are strictly increasing).
This process must terminate, since otherwise we would find an injection from $\sf Ord$ into $B^A$, which is impossible.
(You might want to naively consider for each $b\in B$ the set of functions that $b$ is in their range, then choose such function, and choose some $a$ mapped to $b$ by that function. But there is no guarantee that the choices are coherent, you might have chosen the same $a$ all the time.
Instead you need some gluing mechanism, be it Zorn's lemma, Teichmuller-Tukey lemma, or as I wrote here, transfinite recursion. These mechanisms allow you to ensure that at the end, the result is a function.)
A: Let me try to provide a proof which starts from scratch, and using Zorn's Lemma:
Set
$$
{\mathcal F}=\{\,f:A_1\to B, \,\,\text{where $f$ is an 1-1 function, and $A_1\subset A$}\}
$$
This set is partially order by "$\subset$",  as every element of ${\mathcal F}$ is itself a set of ordered pairs, and subset of $A\times B$ - i.e., $f=\big\{\big(a,f(a)\big): a\in Dom(f)\big\}$.
It is easy to check that, if ${\mathcal C}\subset{\mathcal F}$  is a chain, i.e., for every $f,g\in\mathcal C$, either $f$ is an extension of $g$ (i.e., $g\subset f$) or $g$ is an extension of $f$ (i.e., $f\subset g$), then $\bigcup \mathcal C\subset\mathcal F$. That is, the union of an arbitrary family of comparable 1-1 functions (extending one another),is also an 1-1 function. Therefore, Zorn's Lemma applies and provides a maximal such function
$$
f_{\mathrm{max}} : A_0\to B,
$$
with $A_0\subset A$. If $f_{\mathrm{max}}$ is onto, then we are done, as we can extend $f_{\mathrm{max}}$ mapping $A\setminus A_0$ to a specific elements $b_0\in B$.
If $f_{\mathrm{max}}$ is not onto, then let $b_0\in B\setminus f[A_0]$. Also, the domain of $f_{\mathrm{max}}$ is not  the whole of $A$, otherwise we would have an $f_{\mathrm{max}}:A\to B$, which is 1-1. So chose $a_0\in A\setminus A_0$, and define
$$
f_1=f_{\mathrm{max}}\cup\{(a_0,b_0)\},
$$
clearly $f_1$ is 1-1, with domain $A_0\cup\{a_0\}$, and
$$
f \subsetneq f_1,
$$ 
which contradict the fact that $f_{\mathrm{max}}$ is a maximal element of ${\mathcal F}$.
Therefore, $f_{\mathrm{max}}$ is onto, and 
$$
\hat f=f_{\mathrm{max}}\cup \big(A\setminus A_0\big)\times\{b_0\} : A\to B,
$$
is also an onto function.
A: I think the key point here is that there is no mapping from A to B that is injective, without knowing anything else about sets A and B. In other words there is no way we can construct an injective mapping from A to B. If they are finite, the only way that this can be true is only if |B|<|A| so no matter how we try there will always exist an element b in B such that: $ a_1 a_2\in A, f(a_1)=b=f(a_2) $ assuming f is a total function. Or if B is finite and A infinite. In any case if it is impossible for an injection to exist, set A must have a higher cardinality than set B; more elements. For if A has fewer elements than B I don't see a way that a injection cannot exist.
I think this come down to the more general 'axiom of choice' and its equivalent form: for sets A, B either $|A|\leq|B|\: or\: |B|\leq|A|$ as stated by Asaf.
If $|A|\leq|B|$ then must exist an injective function from A to B, so this is not the case and by the theorem must hold that $|B|\leq|A|$ and exists a function $f:B\rightarrow A$ that is injective and must exist a function $g:A\rightarrow B$ that is surjective.
If we do not accept the axiom of choice (or Zorn's lemma) how can you choose the elements for the construction of your surjection? If I have understood the axiom of choice, if you say something like $g(a)$='the first element b from B that ...' is invoking the axiom of choice. Where '...' you put what you want, like 'is bigger than g(a-1)' or 'is the first b such that there exist no a in A: g(a)=b' or 'find a random element in A, check if it has been given a pair from A, if not return it else find another'. All these are implying the axiom of choice.
So I we know nothing for A and B, e.g. if the can be ordered or any other information, and you cannot use the axiom of choice then I would say you cannot prove that such a surjection exists. 
