Difference between revisions of "SP20:Lecture 7 'Jectivity and inverse functions"
(Created page with "= Function equality = {{:Equality (functions)}} = Inverse functions = Inverse functions capture the idea of "flipping a function over". To give the formal definition o...") |
m (<math>'"1 {{GENDER:Mdg39|moved}} page </math>'"3 to SP20:Lecture 7 'Jectivity and inverse functions) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | We discussed some important definitions related to [[function]]s: [[equality (functions)|function equality]], [[function composition]], the [[identity function]] and [[inverse (function)|inverse functions]]. | ||
| + | |||
| + | * Last semester this was covered in [[FA19:Lecture 6 Injectivity and left inverses|lecture 6]] and [[FA19:Lecture 7 Surjectivity and Bijectivity|lecture 7]] | ||
| + | * [[Media:sp20-lec07-slides.pdf|slides]] | ||
| + | |||
= Function equality = | = Function equality = | ||
| Line 9: | Line 14: | ||
{{:Composition}} | {{:Composition}} | ||
| − | {{:Identity | + | We will also use the definition of the [[identity function]] to formally define [[inverse (function)|inverses]]: |
| + | |||
| + | {{:Identity function}} | ||
== Left inverses == | == Left inverses == | ||
Latest revision as of 13:18, 17 February 2020
We discussed some important definitions related to functions: function equality, function composition, the identity function and inverse functions.
Contents
Function equality
Inverse functions
Inverse functions capture the idea of "flipping a function over". To give the formal definition of an inverse, we start with some preliminary tools for putting functions together:
One way to combine functions together to create new functions is by composing them:
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
).
For example,
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.
We will also use the definition of the identity function to formally define inverses:
Left inverses
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 ):
In other words, for all , .
Right inverses
In other words, for all , .
is a right inverse of because you write it to the right of to get the identity.
Two-sided inverses
If has a two-sided inverse, it must be unique, so we are justified in writing the two-sided inverse of . We also write to denote the inverse of if it exists.
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:
- 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
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.
It is sensible to check that is a bijection. The reason a bijection is desirable is because it has a two-sided inverse which can be used to convert the file back into the original format.
If is not injective, then it is "lossy": some information about the original file is lost.
If is not 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.
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'.
If you want to provide an undo/redo capability, then the functions should be bijections. If they are, then their two-sided inverses give the undo operations.
Sometimes you can make a function into a bijection by adding an "undo log": by expanding the set you can keep enough history to implement an undo function.
