# Proof:Surjections have right inverses

Let

We want to construct an inverse for ; obviously such a function must map to a, but we have a choice of where to map . We can't map it to both and (because then would be ambiguous), but we can just pick one of them (say ).

So we have

Then we plug into the definition of right inverse and we see that and , so that is indeed a right inverse.

Note that this wouldn't work if was not surjective, (for example, if had no pre-image) we wouldn't have any output for (so that wouldn't be total).

Here is the general proof:

Proof: surjections have right inverses
Choose an arbitrary , , and a surjection . We want to show that there exists a right inverse of .

Define on input as follows: we know that there exists at least one with , since is surjective. Choose one of them and call it .

Note: it is not clear that there is an unambiguous way to do this; the assumption that it is possible is called the axiom of choice.

Now, we must check that is a right inverse of , i.e. that .

Choose an arbitrary . We have by definition of . Therefore

as required.