Choose <injections> $a:X\to\mathbb N$ and $b:Y\to\mathbb N$. The map $(x,y)\mapsto(a(x),b(y))$ is an <injection> into the <countable set> $\mathbb N\times\mathbb N$. Composing with the <Cantor pairing function> gives an <injection> into $\mathbb N$. Thus \b[the Cartesian product of two countable sets is countable], including the case of an empty factor.

Solution

Past exam of the mathematics course of the University of Cambridge / 2015 / ia / Paper 4 / 8E / b / i / Solution

 Solution (source code)