Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 7E / i / Solution

Use “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.