Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 4 / 5E (Numbers and Sets)

A left inverse of $f$ is a function $\ell :B\to A$ satisfying $\ell \circ f={\mathrm{id}}_A$. If such $\ell$ exists and $f(a)=f(a^{\prime })$, applying $\ell$ gives $a=a^{\prime }$, so $f$ is an injection. Conversely, suppose $f$ is an injection and fix $a_0\in A$, possible because $A$ is nonempty. DefineThe first value is unique by injectivity, and $\ell (f(a))=a$ for every $a$. ThusNo choice from a family of nonempty sets is needed here: each preimage in the first case is unique, and the second case uses one fixed element.

A right inverse is a function $r:B\to A$ with $f\circ r={\mathrm{id}}_B$. Its existence makes every $b$ the image of $r(b)$, proving that $f$ is a surjection. Conversely, if $f$ is a surjection, every fiber of a function $f^{-1}(\{b\})$ is nonempty. Using the usual axiom of choice for arbitrary sets, choose $r(b)\in f^{-1}(\{b\})$ for each $b$. Then $f(r(b))=b$, givingThe converse in this second equivalence is the right-inverse characterization of the axiom of choice; it is not an unrestricted choice-free theorem about arbitrary sets.

Choose a right inverse $s:A\to B$ of the surjection $f$, so $f(s(a))=a$, and defineFor each $a$, the element $b=s(a)$ then witnesses both $f(b)=a$ and $g(b)=h(a)$. As in part (a), arbitrary simultaneous choices use the axiom of choice. If $A$ is empty, surjectivity and the existence of $f:B\to A$ force $B$ to be empty, and the unique empty function $h:A\to C$ already meets the requirement.

Suppose $g$ is constant on each fiber of a function of $f$. Since every fiber is nonempty, $h(a)$ must be its common $g$-value: any witness $b$ in that fiber gives that value. This defines exactly one $h$ and yields $g=h\circ f$, an instance of factorization through a surjection.

Conversely, suppose a fiber contains $b,b^{\prime }$ with $f(b)=f(b^{\prime })=a_0$ but $g(b)\ne g(b^{\prime })$. Starting with any admissible $h$, define $h_1,h_2$ to agree with it away from $a_0$, but put $h_1(a_0)=g(b)$ and $h_2(a_0)=g(b^{\prime })$. Both remain admissible, witnessed at $a_0$ by $b$ and $b^{\prime }$ respectively, yet they are distinct. HenceThe distinction is important: the original existence property asks only for one witness in each fiber. Only when $g$ is fiberwise constant does that property force $g=h\circ f$ for every $b$.