Proof:Injections have left inverses

If and is injective, then has a left inverse.

Proof: injections have left inverses

To demonstrate the technique of the proof, we start with an example.

Let [math]f := [/math]

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

So we have [math]g := [/math]

Then we plug [math]g [/math] into the definition of left inverse and we see that and , so that [math]g [/math] is indeed a left inverse.

Note that this wouldn't work if [math]f [/math] was not injective. For example,

if [math]f := [/math]

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

Here is the general proof:

Choose an arbitrary , [math]B [/math], and an injection . We want to show that there exists a left inverse [math]g [/math] of [math]f [/math].

Let [math]x_0 [/math] be an element of [math]A [/math] (we know that such an element exists because ).

Let be given by

[math]g [/math] is well defined, because if [math]f(x_1) = y [/math] and [math]f(x_2) = y [/math] then [math]x_1 = x_2 [/math] (since [math]f [/math] is injective). Thus the output of [math]g [/math] is unambiguous.

To see that [math]g [/math] is a left inverse of [math]f [/math], choose an arbitrary ; we have

so , which is the

definition of a left inverse.