Past exam of the mathematics course of the University of Cambridge / 2022 / ia / Paper 4 / 8F / b

List pairs $(m,n)\in {\mathbb{N}}^2$ by increasing value of $m+n$, and within each diagonal by increasing $m$:Every pair occurs after finitely many earlier diagonals. More explicitly, the Cantor pairing functionis an injection ${\mathbb{N}}^2\to \mathbb{N}$. Hence $\mathbb{N}\times \mathbb{N}$ is countable.

The integers are countable under the enumerationPart (i) then shows that $\mathbb{Z}\times \mathbb{N}$ is countable. The mapis a surjection from $\mathbb{Z}\times \mathbb{N}$ onto the rational numbers. Selecting, for example, the representation in lowest terms with positive denominator gives an injection in the other direction. Thus $\mathbb{Q}$ is countable.

For a increasing function $F$, define its one-sided limits byThey exist because of monotonicity. The function is discontinuous at $x$ only if the jump intervalis nonempty. By the density of the rational numbers, choose $q_x\in J_x\cap \mathbb{Q}$.

If $x<y$, monotonicity gives $F(x+)\le F(y-)$, so $J_x$ and $J_y$ are disjoint. Consequently $q_x\ne q_y$, and $x\mapsto q_x$ injects the set of discontinuities into $\mathbb{Q}$. Since the rationals are countable by part (ii), the set of discontinuities is countable.