The set of algebraic numbers is countable.

real-analysis

I'm currently working through Rudin's PMA, and I'm on exercise 2.2 which tasks me to prove that the set of algebraic numbers is countable. There is a hint we are given to use, which is that the number of equations that satisfy the equation
$n + |a_0| + \cdots + |a_n| = N$ for any positive integer $N$ is finite. Now, here was my thought process:

  1. Establish a set of $(n + 1)$-tuples consisting of the elements $(n, a_0, a_1, \ldots, a_n)$, where $n$ is a positive integer, and $a_i$ is any integer, not all $0$, such that the hint is satisfied; call these sets $C_N$.
  2. Let $P_N$ be the set of polynomials with complex inputs whose coefficients satisfy the above hint. Then $P_N$ is finite.
  3. Let $R_N \subset P_N$ be the set of polynomials that have a root at $z = 0$. Since $P_N$ is finite, then $R_N$ is finite.
  4. Let $A_N$ denote the set of complex numbers that satisfy a polynomial in $R_N$. Since any $n$-degree polynomial has at most $n$ roots, then $A_N$ is also finite.
  5. Take the union of $A_N$ over all positive integers $N$. Then this set is countable, since a union of countable sets is countable.

Please let me know if my logic is right!

Edit: Thank you for the advice removing Step 3. I think I just took an unnecessary, isolating step. This answer would be wrong, since I'm not considering polynomials who have no roots at 0. Thanks a lot for everyone helping!

Best Answer

Let $f(x)$ denote a polynomial $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ with integral coefficients. Now all the real roots of $f(x)$ are algebraic numbers.

For every $f(x)$ we associate an integer $N$ defined as $$N=n+|a_0|+|a_1|+\cdots+|a_{n}|$$

Evidently $N\ge1$ and for any given $N$ only a finite number of polynomials have the given value (the given hint).

Each polynomial has atmost $n$ real roots so any value of $N$ can be associated with a finite number of roots. So now the set of algebraic numbers is the union of roots for each $N$.

So the set of algebraic numbers is a countable union of finite sets so the set of algebraic numbers is countable.

NOTE:

This for the most part agrees with your proof as i understand it except STEP-3

Related Question