SP18:Lecture 7 Inverses

From CS2800 wiki
Revision as of 22:27, 28 February 2018 by {{GENDER:Sy536|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

We will show the relationship between 'jectivity and the existence of inverse functions.

More function definitions

We start with some definitions.


One way to combine functions together to create new functions is by composing them:

Definition: Composition
Given a function [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] and a function [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math], the composition of [math]g [/math] with [math]f [/math] (written [math]g \href{/cs2800/wiki/index.php/%E2%88%98}{∘} f [/math]) is the function [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} C [/math] given by [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(a) := g(f(a)) [/math].

Note that (with the domains and codomains described above), [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g [/math] is not defined; it is impossible to take outputs of [math]g [/math] (which live in the set [math]C [/math]) and pass them into [math]f [/math] (whose domain is [math]A [/math]).

For example, Composition.svg

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.

The identity function

The identity function is a simple but useful function (in fact, it is a bijection):

Definition: Identity function
If [math]A [/math] is a set, then the identity function on [math]A [/math] (written [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id}_A [/math] or simply [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math] if [math]A [/math] is clear) is the function [math]\href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] given by [math]id(x)\href{/cs2800/wiki/index.php/Definition}{:=x} [/math].


left inverses

Given a function [math]f:A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], it is useful to ask whether the effects of [math]f [/math] can be "undone". A reasonable way to define this is to provide an "undo" function [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] such that [math]g(f(x)) = x [/math] for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math]. Such a function is called a left inverse of [math]f [/math] (so-called because you write it on the left of [math]f [/math]):

Definition: Left inverse
Given a function [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], a left inverse [math]g [/math] of [math]f [/math] is a function [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] satisfying [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math].

In other words, for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math], [math]g(f(x)) = x [/math].

right inverses

Similarly, we can talk about functions that [math]f [/math] "undoes":

Definition: Right inverse
Given a function [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], a right inverse [math]g [/math] of [math]f [/math] is a function [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] satisfying [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math].

In other words, for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math], [math]f(g(x)) = x [/math].

[math]g [/math] is a right inverse of [math]f [/math] because you write it to the right of [math]f [/math] to get the identity.

two-sided inverses

Definition: Two-sided inverse
If [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] is a function, then [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] is a two-sided inverse of [math]f [/math] if [math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id}_B [/math] and [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f \href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id}_A [/math].

If [math]f [/math] has a two-sided inverse, it must be unique, so we are justified in writing the two-sided inverse of [math]f [/math]. We also write [math]f^{\href{/cs2800/wiki/index.php/-1}{-1}} [/math] to denote the inverse of [math]f [/math] if it exists.


If [math]f \href{/cs2800/wiki/index.php/Definition}{:=} [/math] Fun-abc-12-a1b2c2.svg and [math]g \href{/cs2800/wiki/index.php/Definition}{:=} [/math] Fun-12-abc-1a2b.svg then [math]f [/math] is a left inverse of [math]g [/math], because

[math]f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g \href{/cs2800/wiki/index.php/Equality_(functions)}{=} [/math] Fun-id-12.svg [math]\href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math]

For the same reason, [math]g [/math] is a right inverse of [math]f [/math].

However, [math]f [/math] is not a right inverse of [math]g [/math] (nor is [math]g [/math] a left inverse of [math]f [/math]) because

[math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f \href{/cs2800/wiki/index.php/Equality_(functions)}{=} [/math] Fun-abc-abc-aabbcb.svg [math]\href{/cs2800/wiki/index.php/Equality_(functions)}{\neq} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math]

Finally, if [math]h := [/math] Fun-abc-123-a2b3c1.svg and [math]i := [/math] Fun-123-abc-1c2a3b.svg, then [math]h [/math] and [math]i [/math] are two-sided inverses of each other, because

[math]h \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} i \href{/cs2800/wiki/index.php/Equality_(functions)}{=} [/math] Fun-id-123.svg [math]\href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math] and [math]i \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} h \href{/cs2800/wiki/index.php/Equality_(functions)}{=} [/math] Fun-id-abc.svg [math]\href{/cs2800/wiki/index.php/Equality_(functions)}{=} \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math]

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:


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.

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.