An algebraic number over the field of rationals is defined as any root of a polynomial with real coefficients. That is an $x$ such that $p(x)=0$ where $p(x)$ is of the form $x^n+a_{n-1}x^{n-1}+...+a_1x+a_0$, with $a_i\in\mathbb{Q}$, and $n\in\mathbb{N}$.

I am asked to prove the following:

Show that the set of algebraic numbers over the field of rationals is countable. You may assume that set of roots for any given polynomial over the field of rationals is finite.

(This is Excercise 4.a) from Munkres' Topology 2e.)

Several proofs of this exist on this site and elsewhere. However, I am wondering if my particular proof of this fact is acceptable. (I searched but I couldn't find this exact proof; if it's a duplicate please let me know and I'll flag my question for closing.)

Here is my proof:

We have that a polynomial of fixed degree $n$ over the field of rationals can be written as $$x^n+a_{n-1}x^{n-1}+...+a_1x+a_0.$$ This may be represented as an $n$-tuple $(1,a_{n-1},...,a_1,a_0)$. Clearly, this is a subset of the Cartesian product of $\mathbb{Q}$ with itself $n$ times. That is, it is a subset of $\mathbb{Q}^n$. By a theorem (7.6), we know that the finite Cartesian product of countable sets is countable. Since, $\mathbb{Q}$ is countable, it follows that $\mathbb{Q}^n$ for fixed $n$ is countable. By a corollary (7.3), we also know that any subset of a countable set is countable, so the set of polynomials of degree $n$ is countable. By yet another theorem (7.5), we have that the countable union of countable sets is countable, so we have that the set of all polynomials, denoted by $$\bigcup\limits_{n\in\mathbb{N}}(\text{the set of all polynomials of degree }n),$$ is countable.

Now, given that each polynomial has finitely many (and hence countably many roots), it folllows by another application of (7.5) that the set of all roots (i.e. algebraic numbers over the field of rationals) is countable.

Is this an acceptable proof?

  • $\begingroup$ I think this seems like the proof here except they are working with complex numbers and integer coefficients. I don't know too much about this topic, but hopefully this helps. $\endgroup$ – W. Ryan Jan 20 '19 at 1:52
  • 1
    $\begingroup$ Algebraic numbers are roots of polynomials with rational, not real, coefficients. Given lines 3 and 4 of your proof, I think you had this in mind. There are $n+1$ coefficients for a polynomial of degree $n.$ Other than these minor points, the proof looks pretty good from a quick read. $\endgroup$ – Chris Leary Jan 20 '19 at 1:58
  • $\begingroup$ And to make the algebraic numbers enumerable you can see $\overline{\mathbb{Q}}$ as a subfield of $\mathbb{C}$ and identify an algebraic number with the data of a polynomial $f\in \mathbb{Z}[X]$ whose it is a root together with a disk $\subset \mathbb{C}$ where $f$ has exactly one root $\endgroup$ – reuns Jan 20 '19 at 2:01

Off the top of my head, I would argue (ignoring that OP wanted their proof checked and was not seeking another) that each rational is a pair of integers so using this pair as exponents of a pair of primes (and maybe using a third prime to represent the sign) allows us to show that the set of such polynomials is countable.

Once we have that we can again use the prime trick to map the polynomials and the degree into the integers to show that is countable.

The details undoubtedly have already been worked out many years ago.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.