Past exam of the mathematics course of the University of Cambridge / 2008 / ia / Paper 4 / 5D / b / Solution

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.