Past exam of the mathematics course of the University of Cambridge / 2002 / ia / Paper 4 / 1C (Numbers and Sets)

An injective function satisfies $f(a)=f(a^{\prime })\Rightarrow a=a^{\prime }$ for all $a,a^{\prime }\in A$. A surjective function $g:A\to B$ satisfies: for every $b\in B$, some $a\in A$ has $g(a)=b$. The following arguments apply to function composition with the stated domains and codomains.

Let $c\in C$. Since $g$ is surjective, choose $b\in B$ with $g(b)=c$. Since $f$ is surjective, choose $a\in A$ with $f(a)=b$. Then $(g\circ f)(a)=g(b)=c$. Thus every element of $C$ has a preimage, proving that $g\circ f$ is surjective.

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. The injectivity of $g$ implies $f(a)=f(a^{\prime })$, and the injectivity of $f$ then implies $a=a^{\prime }$. Hence $g\circ f$ is injective.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. The injectivity of $g\circ f$ implies $a=a^{\prime }$, so $f$ is injective.

For any $c\in C$, the surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Therefore $f(a)\in B$ is a preimage of $c$ under $g$, proving surjectivity of $g$.

For the requested counterexample, take $A=C=\{0\}$, $B=\{0,1\}$, $f(0)=0$, and $g(0)=g(1)=0$. The function composition is the identity bijection of the singleton, but $f$ is not surjective and $g$ is not injective.