Exercise 2.5

In what follows we suppose that $f:A\to B$.

(a)

Proof. First, suppose that $f$ has a left inverse $g:B\to A$ so that $g\circ f=i_A$. Consider any $x,y\in A$ where $f(x)=f(y)$. Then we have

$$\begin{array}{cc}x=i_A(x)=(g\circ f)(x)=g(f(x))=g(f(y))=(g\circ f)(y)=i_A(y)=y,& \end{array}$$

which shows that $f$ is injective by definition.

Now suppose that $f$ has a right inverse $h:B\to A$ so that $f\circ h=i_B$. Consider any $y\in B$ so that

$$\begin{array}{cc}y=i_B(y)=(f\circ h)(y)=f(h(y)).& \end{array}$$

Then $x=h(y)$ is an element of $A$ such that $f(x)=y$, which shows that $f$ must be surjective since $y$ was arbitrary. □

(b)

Consider the sets $$\begin{array}{llllllll}\hfill A& =\left\{1,2\right\}& \hfill B& =\left\{a,b,c\right\}& \hfill & & \hfill & \end{array}$$

and the function $f=\left\{(1,a),(2,b)\right\}$. Define the function $g:B\to A$ by $g=\left\{(a,1),(b,2),(c,2)\right\}$. It is easy to see that this is a left inverse of $f$ since we have

$$\begin{array}{llllllll}\hfill (g\circ f)(1)& =g(f(1))=g(a)=1& \hfill (g\circ f)(2)& =g(f(2))=g(b)=2& \hfill & & \hfill & \end{array}$$

so that $g\circ f=i_A$.

Also, note that clearly, $f$ is not surjective since there is no element of $A$ that maps to $c\in B$. This suffices to show that $f$ cannot have a right inverse since, if it did, then it would have to be surjective by part (a).

(c)

Now define the sets $$\begin{array}{llllllll}\hfill A& =\left\{1,2,3\right\}& \hfill B& =\left\{a,b\right\}& \hfill & & \hfill & \end{array}$$

and the function $f=\left\{(1,a),(2,b),(3,a)\right\}$. Define the function $h:B\to A$ by $h=\left\{(a,1),(b,2)\right\}$. Then we have

$$\begin{array}{llllllll}\hfill (f\circ h)(a)& =f(h(a))=f(1)=a& \hfill (f\circ h)(b)& =f(h(b))=f(2)=b& \hfill & & \hfill & \end{array}$$

so that clearly $f\circ h=i_B$, and hence $h$ is a right inverse of $f$.

Note, however, that $f$ is not injective since $f(1)=a=f(3)$. This suffices to show that $f$ cannot have a left inverse since, if it did, it would be injective by part (a).

(d)

We claim that a function can have more than one right or left inverse.

Proof. To show that a function can have more than one left inverse consider the example constructed in part (b). Recall that this consists of the sets

$$\begin{array}{llllllll}\hfill A& =\left\{1,2\right\}& \hfill B& =\left\{a,b,c\right\}& \hfill & & \hfill & \end{array}$$

and the function $f=\left\{(1,a),(2,b)\right\}$. It was shown there that the function $g_1=\left\{(a,1),(b,2),(c,2)\right\}$ is a left inverse. Let $g_2=\left\{(a,1),(b,2),(c,1)\right\}$ so that clearly $g_1\ne g_2$ since $g_1(c)=2\ne 1=g_2(c)$. It is trivial to show that $g_2$ is also a left inverse of $f$, which shows that more than one left inverse exists for this $f$.

To show that a function can have more than one right inverse, consider the example in part (c), which is the sets

$$\begin{array}{llllllll}\hfill A& =\left\{1,2,3\right\}& \hfill B& =\left\{a,b\right\}& \hfill & & \hfill & \end{array}$$

and the function $f=\left\{(1,a),(2,b),(3,a)\right\}$. It was shown there that the function $h_1=\left\{(a,1),(b,2)\right\}$ is a right inverse. Let $h_2=\left\{(a,3),(b,2)\right\}$ so that clearly $h_1\ne h_2$ since $h_1(a)=1\ne 3=h_2(a)$. However, it is trivial to show that $h_2$ is also a right inverse of $f$, from which the desired result follows. □

(e)

Note that what follows proves Lemma 2.1 in the text, which is not proven there.

Proof. Suppose that $f$ has left inverse $g$ and right inverse $h$. Then $f$ must be both injective (since it has a left inverse) and surjective (since it has a right inverse) so that it is bijective by definition. Then of course the function $f^{-1}:B\to A$ exists. Consider any $y\in B$ and set $x=f^{-1}(y)$ so that $y=f(x)$. Then we have that

$$\begin{array}{cc}g(y)=g(f(x))=(g\circ f)(x)=i_A(x)=x& \end{array}$$

since $g$ is a left inverse of $f$. We also have

$$\begin{array}{cc}f(h(y))=(f\circ h)(y)=i_B(y)=y& \end{array}$$

so that

$$\begin{array}{cc}h(y)=f^{-1}(f(h(y))=f^{-1}(y)=x.& \end{array}$$

This shows that $x=f^{-1}(y)=g(y)=h(y)$, which in turn shows that $f^{-1}=g=h$ as desired since $y$ was arbitrary. □