Proof:Surjections have right inverses

From CS2800 wiki
Revision as of 16:30, 3 March 2020 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)
If [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math] is surjective, then [math]f [/math] has a right inverse.

To demonstrate the proof, we start with an example.

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

We want to construct an inverse [math]g:\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b,c\}} [/math] for [math]f [/math]; obviously such a function must map [math]1 [/math] to a, but we have a choice of where to map [math]2 [/math]. We can't map it to both [math]b [/math] and [math]c [/math] (because then [math]f [/math] would be ambiguous), but we can just pick one of them (say [math]b [/math]).

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

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

Note that this wouldn't work if [math]f [/math] was not surjective, (for example, if [math]2 [/math] had no pre-image) we wouldn't have any output for [math]g(2) [/math] (so that [math]g [/math] wouldn't be total).

Here is the general proof:

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

Define [math]g : B \href{/cs2800/wiki/index.php/%E2%86%92}{→} A [/math] on input [math]y [/math] as follows: we know that there exists at least one [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A [/math] with [math]f(x) = y [/math], since [math]f [/math] is surjective. Choose one of them and call it [math]g(y) [/math].

Note: it is not clear that there is an unambiguous way to do this; the assumption that it is possible is called the axiom of choice.

Now, we must check that [math]g [/math] is a right inverse of [math]f [/math], i.e. that [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].

Choose an arbitrary [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B [/math]. We have [math](f \href{/cs2800/wiki/index.php/%5Ccirc}{\circ} g)(y) = y [/math] by definition of [math]g [/math]. Therefore [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]

as required.