5
$\begingroup$

NOTE: I know that countability of algebraic numbers has been proven on this site before, but I'm concerned about this specific hint they give and I don't know how to prove it using that advice.

I am doing an exercise in Rudin to prove that the set of algebraic numbers is countable. In particular,

A complex number is said to be algebraic if there are integers $a_0, \dots, a_n$, not all $0$, such that $a_0 z^n + a_1 z^{n-1} + \dots + a_n = 0$. Prove that the set of all algebraic numbers is countable.

Hint: For every positive integer $N$ there are only finitely many equations with $n + |a_0| + |a_1| + \dots + |a_n| = N$


I have proven the statement using essentially the method in this post, but I'm curious as to how one can use the hint to prove the statement.

$\endgroup$
  • 1
    $\begingroup$ Roger Cooke gives a solution to this problem and the rest in the book: minds.wisconsin.edu/handle/1793/67009 $\endgroup$ – Daniel W. Farlow Jan 30 '15 at 16:57
  • $\begingroup$ @user26857 I usually go back at the end of every month and look through my posts and decide on an accept answer (or give a post a bounty if I think the best answer isn't good enough). I guess I just forgot. $\endgroup$ – MCT Apr 1 '15 at 15:51
7
$\begingroup$

I believe that this hint helps you to establish that $\mathbb Z[X]$ is countable.

For a polynomial $f(X)=a_nX^n+\cdots +a_1X+a_0\in\mathbb Z[X]$, $a_n\neq 0$, define the number $h(f)$ by: $$h(f)= n+|a_n|+\cdots+|a_1|+|a_0|.$$ The function $h:\mathbb Z[X]\longrightarrow \mathbb N$ measures some kind of a complexity of a polynomial.

It is fairly obvious that the set $P_N=\{f(X)\in\mathbb Z[X]\mid h(f)= N\}$ is finite, and that $$\mathbb Z[X]= \bigcup_{N\geq 0}P_N.$$ Hence $\mathbb Z[X]$ is countable union of finite sets, hence countable. (Let me say, very nice trick!)

Now, the usual argument finishes the proof: the set of algebraic numbers is $$\bigcup_{f\in\mathbb Z[X]}\operatorname{roots}(f),$$ and it is countable union of finite sets, hence countable.

$\endgroup$

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.