Htykuut

The problem from Rudin's POMA is reproduced below:

Exercise 2.2: A complex number $z$ is said to be algebraic if there are integers $a_0,ldots,a_n$, not all zero, such that
$$
a_0z^n+a_1z^{n-1}+cdots+a_{n-1}z+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|+cdots+|a_n|=N.
$$

I think I've worked out how to use the hint effectively, but I'm curious as to the justification of the hint itself.

Ideas: Any positive integer $N$ effectively puts a bound on the order of the polynomials under consideration, namely $N-1$. The bound on the order of the polynomial also puts a bound on the number of coefficients being considered regardless of their value. Now, I know that a polynomial of order $n$ has at most $n$ distinct roots--how can I use that to good effect here?

If, say, $N=7$, then the order of the polynomials under consideration can be at most $6$ (otherwise all the coefficients would have to be 0 which is not permitted). If we are looking at a polynomial of degree 6, then we may only have one coefficient with a nonzero value, and that nonzero value would have to be 1.

Am I on the right track here? I'm not sure how to formalize this reasoning (or if it's even worth formalizing).

What Rudin is saying in his usual cryptic fashion is that you should associate to each $N$ a finite set of algebraic numbers (call it $X_N$), and then you should prove that {algebraic numbers} $subset bigcup X_N$.

For example, with $N=2$, you have just two possibilities for integer polynomials:
$n=1, a_0=1, a_1=0$, OR
$n=1, a_0=-1, a_1=0$
corresponding to the polynomials
$z$ and $-z$.

For $N=3$, you have
begin{align*}
n=1, a_0=1, a_1=1 \
n=1, a_0=-1, a_1=1 \
n=1, a_0=1, a_1=-1 \
n=1, a_0=-1, a_1=-1 \
n=2, a_0=1, a_1=0, a_0=0 \
n=2, a_0=-1, a_1=0, a_0=0 \
end{align*}
and all the polynomials which those represent.

Let $X_N$ be the roots corresponding to all the polynomials listed for a given $N$. By (# roots $leq$ degree), and the fact that there is a finite list of polynomials for each $N$, $X_N$ is finite. For instance, you can roughly bound $|X_2|leq2$ and $|X_3|leq 8$ above.

After you've proven that every algebraic number belongs to some $X_N$, you can use the fact that a countable union of countable (finite in this case) sets is countable.

This seems a bit perverse but if you can find the following sets:

For each $n in mathbb N$ there is a set $A_n$ containing at most some finite number of $k_n$ polynomials, and the polynomials are of some maximum $m_n$ degree then there is a set $B_n$ containing most $k_ncdot m_n$ algebraic numbers, and if we can further do this so that $U_{nin mathbb N}A_n$ will contain all possible polynomials then $U_{nin mathbb N}B_n$ will contain all possible algebraic numbers.

And that being a countable union of finite sets is countable.

So all we have to divide all the possible polynomials into these finite sets.

Okay, we can take a polynomial $a_nx^n + .... + a_0$ and come up with a number $N = n + |a_n| + |a_{n-1}| + .... + a_0$. And we'll simply put it in a set called $A_N$. As every polynomial will have such a number every polynomial will get placed and as each number $N$ can only have a finite number of degrees and coefficients adding up to $N$ each $A_N$ is finite.

Ta-da! We are done.

Now if you are like every student I have ever met, you will probably ask well why not just say: For each degree of a polynomial there are only a countable number of coefficients for that possition, so there are only a countable union of countably many coeficients to determine a countable number of polynomials.

I'm not sure why that's not the intended method. I suspect is there is one pitfall, in that is very easy to fall into the trap not noticing polynomials must be finite and making a false conclusion that the set of infinite sequence of integers is countable.