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

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.

Fix a positive rational radius $r$. Distinct disjoint circles of radius $r$ have centers more than $2r$ apart, so their open interior disks are pairwise disjoint. Each such disk contains a point of the countable dense set ${\mathbb{Q}}^2$. Fix an enumeration of ${\mathbb{Q}}^2$ and assign to each disk the first rational point it contains. Disjointness makes this assignment injective, so there are only countably many circles of radius $r$.

The positive rational numbers are countable. Taking the countable union of countable sets over all rational radii proves that the whole collection is countable.

The conclusion remains true, even though the scaling factor and hence the radius may now be arbitrary. At the point where its handle meets its circle, every lollipop contains a simple triod: take a short arc of the circle in each direction together with a short segment of the handle. Pairwise disjoint lollipops therefore contain pairwise disjoint simple triods. The Moore triod theorem says that every such family in the plane is countable, so