# FA19:Lecture 6 Injectivity and left inverses

We covered the definition of an injective function. We also defined function composition, as well as left inverses. We proved that injections have left inverses and Claim:functions with left inverses are injections.

# Definitions

## Injectivity

Definition: Injective
A function is injective if, for all and , whenever , we have .
one-to-one is a synonym for injective.

A good way of thinking about injectivity is that the domain is "injected" into the codomain without being "compressed". In other words, no two (different) inputs go to the same output.

The following function is not injective:

because and are both 2 (but ).

## Composition and inverses

One way to combine functions together to create new functions is by composing them:

Definition: Composition
Given a function and a function , the composition of with (written ) is the function given by .

Note that (with the domains and codomains described above), is not defined; it is impossible to take outputs of (which live in the set ) and pass them into (whose domain is ).

Note that this picture is not backwards; we draw functions from left to right (the input is on the left, and the output is on the right) but we apply them with the input on the right. This means the symbolic composition looks backwards when you draw a picture. Given a function , it is useful to ask whether the effects of can be "undone". A reasonable way to define this is to provide an "undo" function such that for all . Such a function is called a left inverse of (so-called because you write it on the left of ):

Definition: Left inverse
Given a function , a left inverse of is a function satisfying .

# Injections have left inverses

Proof: injections have left inverses
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).

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,

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.

# Functions with left inverses are injections

If a function has a left inverse , then is injective.
Proof: Functions with left inverses are injective
Assume has a left inverse , so that . We want to show that is injective, i.e. that for all , if then . Choose arbitrary and in , and assume that . Since have , as required.