## One-sided inverses, surjections, and injections

Several commenters correctly answered the question from my previous post: if we have a function $f : A \to B$ and $g : B \to A$ such that $g(f(a)) = a$ for every $a \in A$, then $f$ is not necessarily invertible. Here are a few counterexamples:

• Commenter Buddha Buck came up with probably the simplest counterexample: let $A$ be a set with a single element, and $B$ a set with two elements. It does not even matter what the elements are! There’s only one possible function $g : B \to A$, which sends both elements of $B$ to the single element of $A$. No matter what $f$ does on that single element $a \in A$ (there are two choices, of course), $g(f(a)) = a$. But clearly $f$ is not a bijection.

• Another counterexample is from commenter designerspaces: let $f : \mathbb{N} \to \mathbb{Z}$ be the function that includes the natural numbers in the integers—that is, it acts as the identity on all the natural numbers (i.e. nonnegative integers) and is undefined on negative integers. $g : \mathbb{Z} \to \mathbb{N}$ can be the absolute value function. Then $g(f(n)) = |n| = n$ whenever $n$ is a natural number, but $f$ is not a bijection, since it doesn’t match up the negative integers with anything.

Unlike the previous example, in this case it is actually possible to make a bijection between $\mathbb{N}$ and $\mathbb{Z}$, for example, the function that sends even $n$ to $n/2$ and odd $n$ to $-(n+1)/2$.

• Another simple example would be the function $f : \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$. Then the function $g(n) = \lfloor n/2 \rfloor$ satisfies the condition, but $f$ is not a bijection, again, because it leaves out a bunch of elements.

• Can you come up with an example $f : \mathbb{R} \to \mathbb{R}$ defined on the real numbers $\mathbb{R}$ (along with a corresponding $g$)? Bonus points if your example function is continuous.

All these examples have something in common, namely, one or more elements of the codomain that are not “hit” by $f$. Michael Paul Goldenberg noted this phenomenon in general. And in fact we can make this intuition precise.

Theorem. If $f : A \to B$ and $g : B \to A$ such that $g(f(a)) = a$ for all $a \in A$, then $f$ is injective (one-to-one).

Proof. Suppose for some $a_1, a_2 \in A$ we have $f(a_1) = f(a_2)$. Then applying $g$ to both sides of this equation yields $g(f(a_1)) = g(f(a_2))$, but because $g(f(a)) = a$ for all $a \in A$, this in turn means that $a_1 = a_2$. Hence $f$ is injective.

Corollary. since bijections are exactly those functions which are both injective (one-to-one) and surjective (onto), any such function $f : A \to B$ which is not a bijection must not be surjective.

And what about the opposite case, when there are functions $f : A \to B$ and $g : B \to A$ such that $f(g(b)) = b$ for all $b \in B$? As you might guess, such functions are guaranteed to be surjective—can you see why?