Why the fact that surjective map has an inverse at right is equivalent to axiom of choice?

Question

Suppose $f:A\to B$ is surjective. By definition for all $b\in B$, there is $a_b\in A$ s.t. $b=f(a_b)$. Define $g:B\to A$ by $$g(b)=a_b.$$ Clearly, $g$ is a well defined function, because $g(b)$ has no two different value, and $g(b)\in A$ for all $b$. Therefore, for all $b\in B$, $$f(g(b))=f(a_b)=b,$$ and thus $g$ is invertible at right. Where did I used Axiom of choice ?

Answer 1

You are misleading yourself when you call this $a$ by $a_b$. You're implicitly assuming that this is uniformly identifiable. It is not. Instead, you should think as follows:

A function $f\colon A\to B$ is surjective, if for every $b\in B$ there is some $a\in A$ such that $f(a)=b$.

Can you define $g$ now? $g(b)=a$? What does it even mean? Which $a$? You'd retort with "Well, the one that is sent to $b$ of course". But what if there are many of them? Which one is "the one"?

For example, what is "the enumeration" of a countable set of reals? Clearly each countable set of reals can be enumerated, it's literally the definition of being countable. But which one is "the enumeration"? Or, given $r\in\Bbb R$, which one is the real number $r'$ such that $r-r'$ is rational, and $r'$ is the same for any $r+q$ when $q\in\Bbb Q$?

It's those instances of switching quantifiers where the axiom of choice lies. You need the axiom of choice to prove that there is a uniform way of choosing this enumeration, this $r'$, this $g(b)$. And while you might not quite know which one you ended up with, the rules of logic do let you assign it with a name: $g(b)$.

---

Additional reading:

1. Axiom of Choice and Right Inverse

2. Show that $f$ is right invertible.

3. Axiom of Choice: Where does my argument for proving the axiom of choice fail? Help me understand why this is an axiom, and not a theorem.

Answer 2

When you chose an arbitrary preimage $a_b$ from the set $f^{-1}(b)$ of preimages for every $b\in B,$ you made an infinite number of arbitrary choices (assuming $B$ is infinite of course).