Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 4 / 6D (Numbers and Sets)

A set $A$ is a countable set if there exists an injective function $A\to \mathbb{N}$, with $\mathbb{N}=\{0,1,2,\dots \}$. Equivalently, it is a finite set or has a bijection with $\mathbb{N}$. An infinite countable set is called a countably infinite set.

The empty set is included: the empty function into $\mathbb{N}$ is injective. This convention distinguishes “countable” from “countably infinite” and will also cover the finite threshold sets in the last part.

Use the well-order of the natural numbers to list $A$ in increasing order. Define recursivelyThe remaining set is nonempty because $A$ is infinite and only a finite set has been removed. Each chosen value is larger than the preceding one, so $f$ is an injective function.

To prove it is a surjective function, fix $a\in A$. If $a$ were never selected, every selected minimum would be at most $a$. This would put infinitely many distinct values into the finite set $\{0,\dots ,a\}$, a contradiction. HenceThe increasing enumeration of an infinite subset of natural numbers uses no arbitrary choice: each next element is the uniquely determined minimum.

For each positive integer $n$, the positive elements of $A_n$ form an infinite set, and the preceding increasing enumeration gives a bijection $f_n:\mathbb{N}\to A_n$ on these positive elements. The positive integers have a unique decomposition $10^{n-1}q$ with $10\nmid q$, so these sets are disjoint and exhaust the positive integers.

The printed natural numbers include $0$. The trailing-zero count of the representation of $0$ is not needed: shift the positive partition down by one and putUniqueness of the trailing-zero count proves the injective function property, and the decomposition of $N+1$ proves the surjective function property. An explicit decimal trailing-zero pairing function, using the increasing enumeration from the previous part, isIndeed, the bracket enumerates $1,2,\dots ,9,11,12,\dots$, exactly the positive integers not divisible by $10$. This handles both the positive index $n$ and the element $0$ without silently changing the PDF's convention.

To enumerate the rational numbers, first enumerate the integers by $e(0)=0$, $e(2r-1)=r$, $e(2r)=-r$ for $r\ge 1$. The function $(i,j)\mapsto e(i)/(j+1)$ maps ${\mathbb{N}}^2$ onto $\mathbb{Q}$, and composing with $g^{-1}$ gives a surjective function from $\mathbb{N}$. Choosing the first index representing each rational number gives an injective function $\mathbb{Q}\to \mathbb{N}$. Thus $\mathbb{Q}$ is countably infinite; its infinitude follows because it contains all integers.

For each positive integer $n$, consider the threshold set $A^{(n)}=\{a\in A:a\ge 1/n\}$. If it were infinite, one could choose recursively a sequence of distinct elements from it. Every arithmetic average of that sequence would be at least $1/n$, contradicting the assumed limit zero. Hence every $A^{(n)}$ is a finite set.

Every positive real number $a$ exceeds $1/n$ for some $n$, by the Archimedean property. ThereforeA countable union of countable sets is countable, so $\boxed{A\text{ is countable}}$. In fact, under the stipulated infinitude, $A$ is a countably infinite set. Positivity matters: it ensures that these thresholds cover $A$. This is countability from vanishing averages of distinct sequences; ordinary Cesaro convergence of a sequence of one chosen enumeration would not suffice to control the whole set.