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

A function is injective when $f(x)=f(x^{\prime })$ implies $x=x^{\prime }$. It is surjective when every element of its codomain equals $f(x)$ for at least one element of its domain.

If $g\circ f$ is injective, then $f(x)=f(x^{\prime })$ implieshence $x=x^{\prime }$. Thus injectivity of the composition implies injectivity of the first map.

If $g\circ f$ is surjective, then for every $z\in Z$ there is an $x\in X$ with $z=g(f(x))$. Taking $y=f(x)$ proves that $z$ lies in the image of $g$. Thus surjectivity of the composition implies surjectivity of the second map. The arguments include empty domains and codomains whenever the specified functions exist.

The empty-set cases for Cartesian projections matter here. For $p_i$, write $X_j$ for the other factor. If $X_j$ is nonempty, any $x_i\in X_i$ can be paired with an element of $X_j$, so $p_i$ is surjective. If $X_j$ is empty, the Cartesian product is empty and its image is empty. ConsequentlyThe possibility $X_i=\varnothing$ is included because the empty function onto the empty set is surjective.

If $X_i$ is empty, $p_i$ has empty domain and is injective. If $X_j$ has at most one element, an ordered pair is determined by its $i$th coordinate, so $p_i$ is also injective. Conversely, when $X_i$ is nonempty and $X_j$ contains two different elements, pairing those two elements with one fixed $x_i$ gives distinct ordered pairs with the same projection map. Therefore

The universal property of Cartesian products constructs the desired map pointwise:Its coordinate projection maps are $f_1$ and $f_2$. Any other map with those projection maps must have the same two coordinates at every $y$, and hence must equal $g$. This also covers $Y=\varnothing$.

For joint injectivity of a pair of functions, equality $g(y)=g(y^{\prime })$ means equality of both coordinate images. If either coordinate function is injective, it follows that $y=y^{\prime }$, so $g$ is injective. The converse fails: take $Y=\{a,b,c\}$ and map these points to $(0,0),(0,1),(1,0)$ in $\{0,1{\}}^2$. The paired map is injective, but the first coordinate identifies $a,b$ and the second identifies $a,c$.

There is an empty-factor defect in the printed surjectivity implication. If both $X_1$ and $X_2$ are nonempty and $g$ is surjective, every element of either factor can be completed to a pair and then lifted through $g$. Hence both $f_i$ are surjective. If both factors are empty, existence of the $f_i$ forces $Y$ to be empty and both coordinate maps are again surjective. But takeThen $g:\varnothing \to X_1\times X_2=\varnothing$ is surjective, while $f_1:\varnothing \to \{0\}$ is not. Without a nonempty-factor assumption, the printed implication is false. This is exactly the exception found for the projection maps in part (ii).

Even when both factors are nonempty, the reverse implication fails. For $Y=X_1=X_2=\{0,1\}$, let $f_1(y)=f_2(y)=y$. Both coordinate maps are surjective, but $g(y)=(y,y)$ misses $(0,1)$ and $(1,0)$. Thus coordinate surjectivity does not guarantee that every pair is attained.