Paper 4, Section II, E

(i) What does it mean to say that a function $f: X \rightarrow Y$ is injective? What does it mean to say that $f$ is surjective? Let $g: Y \rightarrow Z$ be a function. Show that if $g \circ f$ is injective, then so is $f$, and that if $g \circ f$ is surjective, then so is $g$.

(ii) Let $X_{1}, X_{2}$ be two sets. Their product $X_{1} \times X_{2}$ is the set of ordered pairs $\left(x_{1}, x_{2}\right)$ with $x_{i} \in X_{i}(i=1,2)$. Let $p_{i}$ (for $\left.i=1,2\right)$ be the function

$p_{i}: X_{1} \times X_{2} \rightarrow X_{i}, \quad p_{i}\left(x_{1}, x_{2}\right)=x_{i}$

When is $p_{i}$ surjective? When is $p_{i}$ injective?

(iii) Now let $Y$ be any set, and let $f_{1}: Y \rightarrow X_{1}, f_{2}: Y \rightarrow X_{2}$ be functions. Show that there exists a unique $g: Y \rightarrow X_{1} \times X_{2}$ such that $f_{1}=p_{1} \circ g$ and $f_{2}=p_{2} \circ g$.

Show that if $f_{1}$ or $f_{2}$ is injective, then $g$ is injective. Is the converse true? Justify your answer.

Show that if $g$ is surjective then both $f_{1}$ and $f_{2}$ are surjective. Is the converse true? Justify your answer.

*Typos? Please submit corrections to this page on GitHub.*