To demonstrate the technique of the proof, we start with an example.
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 left inverse and we see
that and ,
so that is indeed a left inverse.
into the definition of
Note that this wouldn't work if injective. For example,
then the 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 ,
we constructed would need to map to both
and ; if we did both then would be
Here is the general proof:
Choose an arbitrary , , and an
injection . We want to show that there exists
a left inverse of .
Let element of (we know that such an
element exists because ).
Let be given by
well defined, because if and
is injective). Thus the output of is unambiguous.
To see that left inverse of , choose an arbitrary
; we have
, which is the
of a left inverse