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.
Injectivityone-to-one is a synonym for injective.
because but ).and are both 2 (
Composition and inverses
One way to combine functions together to create new functions is by composing them:
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 ):
Injections have left inverses
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).
Note that this wouldn't work if injective. For example,was not
Here is the general proof:
Let be given by
so, which is the definition of a left inverse.