Inverses and 'jectivity

From CS2800 wiki

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:

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 [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math]. You can think of [math]A [/math] as describing the original file format, and [math]B [/math] as describing the new file format.

It is sensible to check that [math]f [/math] is a bijection. The reason a bijection is desirable is because it has a two-sided inverse [math]g [/math] which can be used to convert the file back into the original format.

If [math]f [/math] is not injective, then it is "lossy": some information about the original file is lost.

If [math]f [/math] is not surjective, then the resulting file format has more data than the original. Further edits to the data in the [math]B [/math] format (in other words, functions from [math]B [/math] to [math]B [/math]) 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 [math]A [/math] 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 [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} A [/math] 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 [math]A [/math] you can keep enough history to implement an undo function.