FA19:Lecture 7 Surjectivity and Bijectivity
Relationship between inverses and 'jectivity
You may have noticed a pattern in the examples above. The injective functions seem to have left inverses, and the surjective functions have right inverses; two-sided inverses seem to be connected with bijectivity. Indeed, there is a connection between 'jectivity and inverses, as we will prove in the next lecture:
- injections have left inverses, and functions with left inverses are injective
- surjections have right inverses, and functions with right inverses are surjective
- bijections have two-sided inverses, and functions with two-sided inverses are bijective
We did part of the proof of the first part of the first claim. You can see the first part of all three claims by clicking on them; the second parts are left as an exercise.
example: file formats
Suppose you are writing a program to convert data from one file format to another (or a function to convert one data structure to another). Such a program describes a function . You can think of as describing the original file format, and as describing the new file format.
If injective, then it is "lossy": some information about the original file is lost.is not
If surjective, then the resulting file format has more data than the original. Further edits to the data in the format (in other words, functions from to ) may prevent the object from being mapped back to the original file format.is not
example: user operations
Many user interfaces can be thought of as a collection of functions that transform a document into another document. For example, let be the set of all plain text files. Pressing the 'x' key in a text editor causes an 'x' to be inserted; you can think of this as applying a function that takes the document without the 'x' and outputs the document with the 'x'.
example: solvable equations
One way of understanding surjections and right inverses is as the existence of a solution to an equation. For example, the function given by is not surjective. This is reflected in the fact that you cannot solve the equation for an arbitrary ; indeed, there is no with .