4.II.5D

(a) Define the notion of a countable set, and prove that the set $\mathbb{N} \times \mathbb{N}$ is countable. Deduce that if $X$ and $Y$ are countable sets then $X \times Y$ is countable, and also that a countable union of countable sets is countable.

(b) If $A$ is any set of real numbers, define $\phi(A)$ to be the set of all real roots of non-zero polynomials that have coefficients in $A$. Now suppose that $A_{0}$ is a countable set of real numbers and define a sequence $A_{1}, A_{2}, A_{3}, \ldots$ by letting each $A_{n}$ be equal to $\phi\left(A_{n-1}\right)$. Prove that the union $\bigcup_{n=1}^{\infty} A_{n}$ is countable.

(c) Deduce that there is a countable set $X$ that contains the real numbers 1 and $\pi$ and has the further property that if $P$ is any non-zero polynomial with coefficients in $X$, then all real roots of $P$ belong to $X$.

*Typos? Please submit corrections to this page on GitHub.*