Are we allowed to choose infinite number of elements from an infinite set? 
$f$ is surjective $\implies f$ has right inverse.

Suppose $f$ is surjective. Then for any $b \in B$ there's at least one $a \in A$ such that $f(a) = b$. Choose one such $a$ for each $b$ and define $g: B \implies A$ by letting $g(b)$ the chosen $a$. Then $f(g(b)) = b$, so $f \circ g= 1_B$.
Since surjective functions allow any number of arrows each from different points in the domain onto a single point in the codomain, the proof of the given statement depends on making possibly infinite number of choices (one $a \in A$ with $f(a) = b$ for each $b \in B$). 
Apparently selecting an infinite number of elements is a big deal and a problem. Why is that? Thanks.
 A: The claim that any surjective function has a right inverse is indeed (against standard background assumptions) equivalent to Axiom of Choice. There are whole books on the Axiom of Choice, and on the costs and benefits of accepting it (it has surprising consequences). 
The Wikipedia entry is not a bad place to start finding out more about AC.
And for a more discursive, very informative, article you could read this online encyclopaedia entry.
A: It's not a big deal or a problem, but it does require the Axiom of Choice.
Here's the point. We want to base our math on set theory. In elementary situations sets are just things that have elements, and the way they work is just the way things with elements obviously work. That's the level at which you'd say what's the big deal, we just select one of these and one of those and we have our inverse  function.
But the actual truth is we want to be able to prove things about sets, without any fuzziness about how they work. For that we need axioms; the only things we're allowed to say about sets are things that follow from the axioms. (At least in theory it should be possible for a computer to verify the correctness of a proof, without "understanding" anything. So simply relying on our intuitive ideas about how sets should work is not going to fly - we need axioms, so then we can verify carefully that everything follows from the axioms. So we know exactly what we're assuming.)
Now your inverse function is, like more or less everything else, a set (a function is a set of ordered pairs such that blah blah). And without the Axiom of Choice, the other axioms of set theory simply do not allow you to prove that that set exists.
[Insert here comments already covered in Peter Smith's answer.]
