Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Discrete mathematics, probability and continuous mathematics / 2 / d

Suppose $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of $g$ gives $f(a)=f(a^{\prime })$, and injectivity of $f$ then gives $a=a^{\prime }$. Thus the function composition is injective.

For any $c\in C$, surjectivity of $g\circ f$ supplies $a\in A$ with $g(f(a))=c$. Taking $b=f(a)\in B$ proves that $c$ has a preimage under $g$. Thus $g$ is surjective.

If $f(a)=f(a^{\prime })$, applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Injectivity of the function composition forces $a=a^{\prime }$. Hence $f$ is injective.

Suppose $g(b)=g(b^{\prime })$. Since $f$ is surjective, choose $a,a^{\prime }\in A$ with $f(a)=b$ and $f(a^{\prime })=b^{\prime }$. Then $(g\circ f)(a)=(g\circ f)(a^{\prime })$, so injectivity gives $a=a^{\prime }$ and therefore $b=b^{\prime }$. Thus $g$ is injective. The use of surjectivity is what makes every point of $B$ accessible to this argument.

Fix $b\in B$. Since $g\circ f$ is surjective, there is $a\in A$ with $g(f(a))=g(b)$. Injectivity of $g$ gives $f(a)=b$, proving that $f$ is surjective. All five conclusions are instances of injectivity and surjectivity under composition.