Numbers and Sets | Part IA, 2008

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

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

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

Typos? Please submit corrections to this page on GitHub.