FA19:Lecture 7 Surjectivity and Bijectivity

From CS2800 wiki

We introduced right inverses and surjectivity, and also two-sided inverses and bijectivity. We continued to populate our table of proof techniques

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:

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 [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.

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 [math]f : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] given by [math]f(x) := sin(x) [/math] is not surjective. This is reflected in the fact that you cannot solve the equation [math]f(x) = y [/math] for an arbitrary [math]y [/math]; indeed, there is no [math]x [/math] with [math]f(x) = 7 [/math].

If we restrict the codomain of [math]f [/math] so that the function becomes surjective (i.e. let [math]g : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} → \lt nowiki\gt [-1,1]\lt /nowiki\gt be given by \lt math\gt g(x) := sin(x) [/math]), then there is a right inverse (namely the [math]arcsin [/math] function).