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$.
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$.
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|&lt;|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.