Walter Rudin Exercise 2.2

To prove that the set of all algebraic numbers is countable, the hint provided is that there are finitely many equations of the form $$n+\left|a_0\right|+\left|a_1\right|+\dots+\left|a_n\right|=N. $$ where $a_i$ are coefficients, $n$ is degree of polynomial and $N$ is any positive integer.

How is this analogous to the problem?

  • 1
    $\begingroup$ What are the $|a_i|,n,$ and $N$? Also, do you know that a countable union of countable sets is countable? $\endgroup$ – Guido A. Sep 8 '18 at 5:32
  • $\begingroup$ @GuidoA. I have added the details. Yes, I am aware of that fact. $\endgroup$ – monty singh Sep 8 '18 at 5:38
  • 1
    $\begingroup$ I don't know about "analogous", but it is relevant, in that it implies that you can list all the polynomials. $\endgroup$ – Gerry Myerson Sep 8 '18 at 5:44
  • $\begingroup$ You left out the part before that, where a certain equation was defined, involving variables like $n, a_0, a_1, \dots$. Now, the hint tells us to show, for a given $N$, there are only finitely many of those equations satisfying $n+\left|a_0\right|+\left|a_1\right|+\dots+\left|a_n\right|=N.$. $\endgroup$ – GEdgar Sep 8 '18 at 13:14

I'm not entirely sure of what Rudin meant with the hint, but the general spirit of his approach is that we can separate algebraic numbers in terms of which degree the polynomials they are roots of have, and then separate the polynomials of a given degree in terms of their coefficients. All these will be countable, so when we take the union of them the result will remain countable.

Concretely, let's first see that $\mathbb{Z}_n[X]$ the integers polynomials of grade $n$ are countable: note that the function that maps $a_nX^n + \dots + a_0$ to $(a_n, \dots, a_0) \in \mathbb{Z}^n$ is injective. Furthermore, since

$$ \mathbb{Z}[X] = \bigcup_{n \geq 0}\mathbb{Z}_n[X] \cup \{0\} $$

we have that $\mathbb{Z}[X]$ itself is countable. Finally, the algebraic numbers can be written as the union of the roots of all polynomials with integer coefficients:

$$ \mathbb{A} = \bigcup_{p \in \mathbb{Z}[X] \setminus \{0\}}p^{-1}(0) $$

Each preimage $p^{-1}(0)$ is finite, because $p$ has finite degree, and the union is countable because $\mathbb{Z}[X]$ is, so the result is countable itself.


Show that for any $n\geqslant 1$, the set of roots of polynomials with integer coefficients of degree exactly $n$ is countable, then use that a countable union of countable sets is countable.


An attempt.


$a_0 z^n+ a_1z^{n-1}+...+a_{n -1}z+a_n=0$

where $a_{i}$ , $i=0,1,2,.....n,$ are integers, $a_0\not =0$.

To every polynomial of degree $n$ corresponds a $n$-tuple

$ (a_0,a_1,........, a_{n-1},a_n)$ (bijection).

The set


{$(a_0,a_1,...,a_{n-1},a_n)|a_0 \not =0$}

$\subset \mathbb{Z^{n+1}}$.

As a subset of a countable set,

$T_n$ is countable.

Let $t_{kn} \in T_n, k=1,2,.....$

Every $t_{kn}$ corresponds to a polynomial of degree $n$ which has $n$ roots.

Arrange the roots in dictionary order: $z_1,z_2,.......z_n$.

$ A_n:= ${$(t_{nk}, j)| 1\le j \le n$, $j$ integer, $k=1,2,...$}

is as subset of $T_n×\mathbb{N}$ countable .

Finally :

$\cup_{n} A_n$, countable union of countable sets, is countable.


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.