# Can the composition of two non-invertible functions be invertible?

(Context: I came across this exercise in the textbook "Coding the Matrix" when reading it to supplement my studies in the Coursera class "Coding the Matrix".)

After proving that the composition of invertible functions is itself invertible (by showing that a function is invertible iff it is both one-to-one and onto), the author left as an exercise the proof that the statement "Suppose that $f$ and $g$ are functions and $f \circ g$ is invertible. Then $f$ and $g$ are invertible." is false.

I haven't been able to come up with a solution. Initially, I thought that the image of $g$ would be but a subset of the co-domain of $f$, with the rest of the co-domain of $f$ (say, two elements) mapping to the same element in its domain. This would suffice to make $f$ non-invertible, but $f \circ g$ would still be invertible.

I'm not sure if this is correct, however, because in order for it to be, I'd have to redefine the co-domain of $f \circ g$ to not be the co-domain of $f$.

Is my approach correct? If not, how can the statement be shown to be false?

Your idea is right.

For $f\circ g$ to be invertible, $f$ only needs to be invertible when restricted the range of $g$. It may not actually be invertible on its whole domain. For example, let $g(x)=e^{x}$ and $f(x)=x^{2}$.

Two more general examples: Let $E, F$ be sets, $f\colon E\rightarrow F$. One can prove that:

• $f$ injective $\iff$ there exists a map $\,r\colon F\rightarrow E$ such that $r\circ f=\operatorname{id}_E$ (which is bijective).
• $f$ surjective $\iff$ there exists a map $\,s\colon F\rightarrow E$ such that $f\circ s=\operatorname{id}_F$.

Note

$r$ is then called a retraction of $f$, $s$ is called a section of $f$.

Yes, that is the key. For example, $f\circ g:N\to N, f\circ g(n)=n$, and $g(n)=2n$.

Consider the function $f:\mathbb N \to \mathbb N$ defined by $f(n) = \left \lfloor \dfrac n3 \right \rfloor$, the integer part of $\dfrac n3$. This function is surjective but not injective.

Next consider the function $g:\mathbb N \to \mathbb N$ defined by $g(n) = 3n$. This function is injective but not surjective.

Their composition $(f\circ g) (n) = \left \lfloor \dfrac {3n}3 \right \rfloor = n$ is the identity function.