## 1.2 Exercise 5

After working on these problems all week, I'm not sure I can keep up 1 problem a day.  I'll try to post as many as possible in the span of a week, however.  I'm definitely taking a break over the weekend!

I really like this problem because it was an eye-opener when I first encountered it on the subtleties of inverse mappings.  I've seen it several places, it is a classic exercise on functions.  Here's the problem as taken from Munkres's text:

"In general, let us denote the identity function for a set $C$ by $i_C$.  That is, define $i_C : C \rightarrow C$ to be the function given by the rule $i_C(x) = x$ for all $x \in C$.  Given $f : A \rightarrow B$, we say that a function $g : B \rightarrow A$ is a left inverse for $f$ if $g \circ f = i_A$; and we say that $h : B \rightarrow A$ is a right inverse for $f$ if $f \circ h = i_B$.

(a) Show that if $f$ has a left inverse, $f$ is injective; and if $f$ has a right inverse, $f$ is surjective.

(b) Give an example of a function that has a left inverse but no right inverse.

(c) Give an example of a function that has a right inverse but no left inverse.

(d) Can a function have more than one left inverse? More than one right inverse?

(e) Show that if $f$ has both a left inverse $g$ and a right inverse $h$, then $f$ is bijective and $g=h=f^{-1}$."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 21.)

-----------

SOLUTION

(a)

$f$ not injective means that $f(a) = f(a')$ for $a \neq a'$.  The left inverse exists by hypothesis, and so when we apply it to $f(a)$, by definition $(g \circ f)(a) = a$, and on $f(a')$ it is $(g \circ f)(a') = a'$.  But, being a function, the left inverse must map $f(a) = f(a') = b \in B$ to the same single element in $A$, which would mean $a = a'$. We've reached a contradiction in the argument, so $f$ is injective.

Suppose $f$ is not surjective.  This means there exists a subset of elements $B_{*} \subset B$ that do not map back to themselves via $f$, but then this contradicts the fact that all elements of $B$ come back to themselves after applying $h$ and then $f$. Thus, $f$ must therefore be surjective.

(b)

Many functions are injective but not surjective, say $f: \mathbb{R}^{+} \rightarrow \mathbb{R}$ with rule $\{(x,x) \vert x \in \mathbb{R}\}$.

(c)

Likewise we can find many functions that are surjective but not injective, say $f : [0, \pi] \rightarrow [0,1]$ with rule $\{ (x, sin(x)) \vert x \in \mathbb{R}\}$

(d)

More than one left inverse: yes.  Here's an example: let $f : \{0,1\} \rightarrow \{0, 1, 2\}$ with rule $\{ (0,1) ; (1,2) \}$.  Define $g : \{0,1, 2\} \rightarrow \{0, 1 \}$ by $\{ (0,0) ; (1,0) ; (2,1) \}$.  Another could be $g': \{0,1, 2\} \rightarrow \{0, 1 \}$ by $\{(0,1) ; (1,0) ; (2,1)\}$.  The important thing to notice is that every element of the domain of $f$ is returned to itself after applying $f$ and then $g$ or $g'$.

More than one right inverse: yes.  Consider $f : \{0,1\} \rightarrow \{0\}$ with rule $\{ (0,0) ; (1,0) \}$, and define $h: \{0\} \rightarrow \{0,1\}$ with rule $\{ (0,0) \}$ or $h': \{0\} \rightarrow \{0,1\}$ with rule $\{ (0,1) \}$.  Notice that starting from the domain $B$, applying $h$ or $h'$ on zero, then $f$, returns us to zero: the composition of either function does not move the element in its path to $A$ and back.

(e)

Since $f$ has both a left inverse and a right inverse, it is both injective and surjective, and hence bijective.

To show that $g = h$, pick any element $b \in B$ and apply $h$$h$ is defined on all $B$ (in fact on the image of $f$ by surjectivity, and specifically never outside it).  Furthermore, since $f$ is injective, there is only one way to reach the element $h(b) = a \in A$.  Next pick the same element $b \in B$ and apply $g$.  Since $f$ is surjective, there is no risk of picking a $b$ that is defined to map back to $A$ in the same way as another $b'$-not-in-the-image-of-$f$ under $g$. There is only one way $g$ can map that $b$ into $A$ by the injectivity of $f$, so $g(b) = a$. Since $h$ and $g$ both map to the same element in $A$ for all $b \in B$, $g = h$.  Call this the inverse of $f$, and denote it by $f^{-1}$.  (Note this is different than the preimage of f which uses the same symbol).

Alternatively, by the identity property of equality, $g \circ f \circ h = g \circ f \circ h$.  By associativity of composition of functions, $(g \circ f) \circ h = g \circ (f \circ h)$.  This in turn reduces to $(i_A) \circ h = g \circ (i_B)$, and so $h = g$.

Categories: