Proof:Injections have left inverses

Proof: injections have left inverses
To demonstrate the technique of the proof, we start with an example.

Let

We want to construct an inverse for ; obviously such a function must map to 1 and to 2. We must also define (so that is a function, i.e. total). So we'll just arbitrarily choose a value to map it to (say, 2).

So we have

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

Note that this wouldn't work if was not injective. For example,

if

then the we constructed would need to map to both and ; if we did both then would be ambiguous and thus not a function. If we chose one of the two (say ), then would give the wrong answer on the other ( would be , not ).

Here is the general proof:

Choose an arbitrary , , and an injection . We want to show that there exists a left inverse of .

Let be an element of (we know that such an element exists because ).

Let be given by

is well defined, because if and then (since is injective). Thus the output of is unambiguous.

To see that is a left inverse of , choose an arbitrary ; we have

so , which is the

definition of a left inverse.