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

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

For a countable set $A$, the polynomials of polynomial degree at most $d$ with coefficients in $A$ are described by coefficient tuples in $A^{d+1}$. The finite Cartesian power of a countable set result makes this a countable set. Taking the union over $d\ge 0$ shows there are only countably many such polynomials altogether; restricting to the nonzero polynomials preserves countability.

A nonzero polynomial of polynomial degree $d$ has at most $d$ distinct roots of a polynomial. To see the bound, a root $r$ gives the factorization $P(x)=(x-r)Q(x)$ by the factor theorem, and each other root is a root of $Q$, whose degree is $d-1$; induction starts with a nonzero constant, which has no roots. Thus $\varphi (A)$ is a countable union of countable sets, each of them finite, and is a countable set.

Starting with the given countable set $A_0$, mathematical induction now shows that every $A_n=\varphi (A_{n-1})$ is countable. A final application of the countable union of countable sets theorem givesThis countability argument does not require that the sequence of sets be increasing.

To obtain a countable closure under real polynomial roots, start with $B_0=\{1,\pi \}$ and explicitly retain previous elements at each stage:Part (b) shows that $\varphi$ takes countable sets to countable sets; consequently all $B_n$ and then $X$ are countable by the countable union of countable sets theorem. Also $1,\pi \in X$.

For a nonzero polynomial $P(t)=c_0+\cdots +c_d{t}^d$ with all $c_j\in X$, choose stages $n_j$ containing the finitely many coefficients and put $N={\max }_j{n}_j$. The inclusions $B_n\subseteq B_{n+1}$ ensure that every coefficient belongs to $B_N$. Every real root of a polynomial $P$ therefore belongs to $\varphi (B_N)\subseteq B_{N+1}\subseteq X$. This countable set $X$ has all the required properties. Retaining $B_n$ explicitly avoids assuming the generally false inclusion $A\subseteq \varphi (A)$: for example, $\varphi (\{1\})$ does not contain $1$, since a nonzero polynomial all of whose coefficients are one is positive at $1$.