Past exam of the mathematics course of the University of Cambridge / 2024 / ia / Paper 4 / 8E / a / Solution

A set is countable set if it is finite or admits an enumeration by natural numbers. If $A_n$ are countable, choose enumerations $a_{n,m}$. Since ${\mathbb{N}}^2$ is countable by diagonal enumeration, the array $(n,m)\mapsto a_{n,m}$ enumerates ${\bigcup }_n{A}_n$ after repetitions are removed. This proves that a countable union of countable sets is countable.

The integers are countable, so $\mathbb{Z}\times {\mathbb{N}}_{>0}$ is countable. Mapping $(p,q)$ to $p/q$ surjects onto $\mathbb{Q}$, hence $\mathbb{Q}$ is countable. The same diagonal argument shows that $A\times B$ is countable whenever $A,B$ are.

Finally, if the reals in $(0,1)$ had decimal expansions $x_1,x_2,\dots$, choose a decimal whose $n$th digit differs from the $n$th digit of $x_n$, avoiding digits $0$ and $9$ to remove expansion ambiguity. This number differs from every listed number. The Cantor diagonal argument proves that $\mathbb{R}$ is uncountable.