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?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →