Suppose $f\colon A \to B$ is a function with range $R$. A function $g\colon B\to A$ is a pseudo-inverse of $f$ if for all $b\in R$, $g(b)$ is a preimage of $b$.
Example 4.5.1 If $A=\{1,2,3,4\}$, $B=\{r,s,t\}$ and $$f(1) = r \qquad f(2) = t \qquad f(3) = t \qquad f(4) = r$$ then $R=\{r,t\}$ and $$g(r) = 4 \qquad g(s) = 3 \qquad g(t) = 2 $$ is a pseudo-inverse to $f$; there are others, of course. The important point is that $g$ must map $r$ to either $1$ or $4$, and $t$ to either $2$ or $3$. We will usually be interested in the pseudo-inverse when $f$ is injective or surjective. $\square$
Theorem 4.5.2 If $f$ is injective, any pseudo-inverse is surjective; if $f$ is surjective, any pseudo-inverse is injective.
Proof. Suppose $f$ is injective, and that $a$ is any element of $A$. Then $f(a)$ is an element of the range of $f$, which we denote by $b$. If $g$ is a pseudo-inverse to $f$, then $g(b)$ must be a preimage of $b$, but since $f$ is injective, $b$ has only one preimage, namely $a$. So $g(f(a))=g(b)=a$. In other words, $g\circ f=i_A$ and we say $g$ is a left inverse of $f$. By theorem 4.4.1, $g$ is surjective.
Suppose $f$ is surjective. In this case, $R=B$, so for any $b\in B$, $g(b)$ is a preimage of $b$. This means that $f(g(b))=b$. In other words, $f\circ g=i_B$. We say that $g$ is a right inverse to $f$ when this happens. By theorem 4.4.1, $g$ is injective. $\qed$
Example 4.5.3 If $A=\{1,2,3,4,5\}$, $B=\{r,s,t\}$ and
$$ \begin{array}{} f(1)=r&f(3)=t&f(5)=s\\ f(2)=t&f(4)=r\\ \end{array} $$
then $$ g(r) = 4 \qquad g(s) = 5 \qquad g(t) = 2 $$ is a pseudo-inverse to $f$. It is easy to check that $f\circ g=i_B$. $\square$
Example 4.5.4 If $A=\{1,2,3,4\}$, $B=\{r,s,t,u,v,w\}$ and $$f(1) = s \qquad f(2) = v \qquad f(3) = w \qquad f(4) = r $$ then
$$ \begin{array}{} g(r)=4&g(t)=2&g(v)=2\\ g(s)=1&g(u)=4&g(w)=3\\ \end{array} $$
is a pseudo-inverse to $f$. It is easy to check that $g \circ f=i_A$. $\square$
Exercises 4.5
Ex 4.5.1 Find pseudo-inverses for the following functions:
a) $A=\{1,2,3,4,5,6\}$, $B=\{r,s,t,u\}$
$$ \begin{array}{} f(1)=t&f(3)=u&f(5)=u\\ f(2)=t&f(4)=s&f(6)=s\\ \end{array} $$
b) $A=\{1,2,3,4,5,6\}$, $B=\{r,s,t\}$
$$ \begin{array}{} f(1)=r&f(3)=t&f(5)=s\\ f(2)=s&f(4)=t&f(6)=s\\ \end{array} $$
c) $A=\{1,2,3,4\}$, $B=\{r,s,t,u,v,w\}$
$$ \begin{array}{} f(1)=t&f(3)=u\\ f(2)=r&f(4)=s\\ \end{array} $$
d) $f\colon \R\to \R$, $f(x)=x^2$.
e) $f\colon \R\to \R$, $f(x) =e^x$.
Ex 4.5.2 Determine whether the pseudo-inverses for the functions listed in problem 1 are right inverses, left inverses, both, or neither.
Ex 4.5.3 Prove that every function $f\colon A\to B$ has a pseudo-inverse.
Ex 4.5.4 Give a proof of Theorem 4.4.2 using pseudo-inverses.
Ex 4.5.5 How many pseudo-inverses do each of the functions in 1(a,b,c) have?
Ex 4.5.6 If $g$ is a pseudo-inverse to $f$, what is $f\circ g\circ f$?
Ex 4.5.7 If $A$ has 4 elements and $B$ has 3 elements, what is the least number of pseudo-inverses that a function $f\colon A\to B$ might have? What is the greatest number?