Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 1 / d

The function composition $g\circ f:A\to C$ is defined by $(g\circ f)(a)=g(f(a))$. Suppose $f(a)=f(a^{\prime })$. Applying $g$ gives $(g\circ f)(a)=(g\circ f)(a^{\prime })$. Since the composite is an injective function, $a=a^{\prime }$. Thus $f$ is an injective function.

For each $c\in C$, surjectivity of the function composition gives $a\in A$ such that $g(f(a))=c$. Taking $b=f(a)\in B$ supplies a preimage of $c$ under $g$. Thus $g$ is a surjective function.

Let $h:B\to A$ be a two-sided inverse function of $f$. If $f(a)=f(a^{\prime })$, apply $h$ and use $h\circ f={\mathrm{id}}_A$ to obtain $a=a^{\prime }$, proving injectivity. For any $b\in B$, the other identity gives $b=f(h(b))$, proving surjectivity. Therefore $f$ is a bijection. Both inverse identities matter: a one-sided inverse alone would establish only the corresponding one of these two properties.