Proof:Injections have left inverses

From CS2800 wiki
Revision as of 17:38, 21 February 2018 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)
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.