FA19:Lecture 6 Injectivity and left inverses

From CS2800 wiki
Revision as of 10:55, 23 September 2019 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)

We covered the definition of an injective function. We also defined function composition, as well as left inverses. We proved that injections have left inverses and Claim:functions with left inverses are injections.



Definition: Injective
A function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] is injective if, for all [math]x_1 [/math] and [math]x_2 \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], whenever [math]f(x_1) = f(x_2) [/math], we have [math]x_1 = x_2 [/math].
one-to-one is a synonym for injective.

A good way of thinking about injectivity is that the domain is "injected" into the codomain without being "compressed". In other words, no two (different) inputs go to the same output.

The following function is not injective:


because [math]f(b) [/math] and [math]f(c) [/math] are both 2 (but [math]b \neq c [/math]).

Composition and inverses

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

Injections have left inverses

If [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{\neq} \href{/cs2800/wiki/index.php?title=%5Cemptyset&action=edit&redlink=1}{\emptyset} [/math] and [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] is injective, then [math]f [/math] has a left inverse.
Proof: injections have left inverses
To demonstrate the technique of the proof, we start with an example.

Let [math]f := [/math] Fun-12-abc-1a2b.svg

We want to construct an inverse [math]g:\href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} [/math] for [math]f [/math]; obviously such a function must map [math]a [/math] to 1 and [math]b [/math] to 2. We must also define [math]g(c) [/math] (so that [math]g [/math] is a function, i.e. total). So we'll just arbitrarily choose a value to map it to (say, 2).

So we have [math]g := [/math] Fun-abc-12-a1b2c2.svg

Then we plug [math]g [/math] into the definition of left inverse and we see that [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(1) = 1 [/math] and [math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(2) = 2 [/math], so that [math]g [/math] is indeed a left inverse.

Note that this wouldn't work if [math]f [/math] was not injective. For example,

if [math]f := [/math] Fun-abc-12-a1b2c2.svg

then the [math]g [/math] we constructed would need to map [math]2 [/math] to both [math]b [/math] and [math]c [/math]; if we did both then [math]g [/math] would be ambiguous and thus not a function. If we chose one of the two (say [math]b [/math]), then [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f [/math] would give the wrong answer on the other ([math](g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(c) [/math] would be [math]b [/math], not [math]c [/math]).

Here is the general proof:

Choose an arbitrary [math]A \neq \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math], [math]B [/math], and an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]. We want to show that there exists a left inverse [math]g [/math] of [math]f [/math].

Let [math]x_0 [/math] be an element of [math]A [/math] (we know that such an element exists because [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{\neq} \href{/cs2800/wiki/index.php/%E2%88%85}{∅} [/math]).

Let [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] be given by

[math]g(y) := \left\{\begin{array}{ll} x & \text{if } \href{/cs2800/wiki/index.php/%E2%88%83}{∃x}\href{/cs2800/wiki/index.php/%E2%88%88}{∈}A \text{ such that } f(x) = y \\ x_0 & \text{otherwise} \\ \end{array}\right. [/math]

[math]g [/math] is well defined, because if [math]f(x_1) = y [/math] and [math]f(x_2) = y [/math] then [math]x_1 = x_2 [/math] (since [math]f [/math] is injective). Thus the output of [math]g [/math] is unambiguous.

To see that [math]g [/math] is a left inverse of [math]f [/math], choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math]; we have

[math]\begin{aligned} (g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f)(x) &= g(f(x)) && \text{by definition of }\circ \\ &= x && \text{by definition of }g \\ &= id(x) && \text{by definition of }id \\ \end{aligned} [/math]

so [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], which is the

definition of a left inverse.

Functions with left inverses are injections

If a function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] has a left inverse [math]g : B \href{/cs2800/wiki/index.php/%5Cto}{\to} A [/math], then [math]f [/math] is injective.
Proof: Functions with left inverses are injective
Assume [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] has a left inverse [math]g : B \href{/cs2800/wiki/index.php/%5Cto}{\to} A [/math], so that [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]. We want to show that [math]f [/math] is injective, i.e. that for all [math]x_1,x_2 \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], if [math]f(x_1) = f(x_2) [/math] then [math]x_1 = x_2 [/math]. Choose arbitrary [math]x_1 [/math] and [math]x_2 [/math] in [math]A [/math], and assume that [math]f(x_1) = f(x_2) [/math]. Since [math]g \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} f = \href{/cs2800/wiki/index.php?title=Id&action=edit&redlink=1}{id} [/math] have [math]x_1 = g(f(x_1)) = g(f(x_2)) = x_2 [/math], as required.