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

A set is countable if it is finite or admits an injection into the natural numbers; equivalently, its elements can be listed by a finite list or a sequence.

The product of two countable sets is countable: after choosing enumerations, its elements are indexed by pairs $(m,n)\in {\mathbb{N}}^2$, and these pairs can be listed diagonally. Thus an injection $X\to A\times B$ followed by an injection $A\times B\to \mathbb{N}$ proves that $X$ is countable.

The integers are listed as $0,1,-1,2,-2,\dots$, so $\mathbb{Z}$ is countable. Every rational number is represented by a pair $(p,q)\in \mathbb{Z}\times {\mathbb{N}}_{>0}$, so $\mathbb{Q}$ is countable as the image of a countable set.

Finally, if $A_0,A_1,\dots$ are countable, choose listings $A_n=\{a_{n,0},a_{n,1},\dots \}$, allowing repetitions for finite sets. The diagonal listing of the pairs $(n,m)$ lists every $a_{n,m}$, proving that a countable union of countable sets is countable.