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

A set is countable when it is finite or its elements can be put in one-to-one correspondence with a subset of $\mathbb{N}$. Equivalently, there is an injection from the set into $\mathbb{N}$.

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.

Suppose first that $|A_n|=1$ for every $n>N$. Then an element of $B$ is determined by its first $N$ coordinates, so $B$ is in bijection withA finite Cartesian product of countable sets is countable by repeated application of the diagonal enumeration in part (b)(i). Hence $B$ is countable.

Conversely, suppose infinitely many factors contain at least two elements. Choose increasing indices $n_1<n_2<\cdots$ and distinct elementsFix one element in every remaining factor. Each binary sequence $\epsilon =({\epsilon }_1,{\epsilon }_2,\dots )$ then defines an element of $B$ by placing $a_j^{{\epsilon }_j}$ in coordinate $n_j$ and the fixed element elsewhere. This map is injective.

The set $\{0,1{\}}^{\mathbb{N}}$ is uncountable by Cantor's diagonal argument: from any proposed list of binary sequences, form a new sequence whose $j$th digit differs from the $j$th digit of the $j$th listed sequence. It is absent from the list. Thus $B$ contains an uncountable subset and cannot be countable.

Therefore