Prove algebraic numbers are countable

[JohnDuck]

Homework Statement

"A complex number z is said to algebraic if there are integers a_{0},...,a_{n}, not all zero, such that:

a_{0} z^{n} + a_{1} z^{n-1} +...+ a_{n-1} z + a_{0} = 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_{n}| = N.

Homework Equations

See above.

The Attempt at a Solution

I've constructed a proof by induction that goes as follows: Consider the set A_{1} of algebraic numbers such that a_{0}z + a_{1} = 0. It simply defines the rational numbers, and therefore is countable. Assume the set A_{n} of algebraic numbers s.t. a_{0} z^{n} +...+ a_{n} = 0 is countable. Consider the set of algebraic numbers A_{n+1} s.t. a_{0} z^{n+1} + a_{1} z^{n} +...+ a_{n+1} = 0. Choose a fixed a_{0}=a; then this subset of A_{n+1} can be put in one-to-one correspondence with A_{n} (and is therefore countable). Simply associate each element of this subset with the element of A_{n} in which all of the coefficients are equal (excluding the leading term az^{n+1}). For example, az^{n+1}+3z^{n}+4 = 0 is associated with 3z^{n}+4 = 0. A_{n+1} is the union of all such subsets as a ranges through the integers--and as the union of a countable amount of countable sets, A_{n+1} is countable.

Edit: There's a special case when all the coefficients are equal to zero except a, in which case one cannot use the above method to put this subset in one-to-one correspondence with A_{n}--however, this subset is also countable as it can easily be put in one-to-one correspondence with the integers. Thus A_{n+1} is still countable.

Thus by induction all such A_{n} are countable. The set of all algebraic numbers is the union of all such A_{n} as n ranges through the natural numbers, and thus is countable.

My question then is not how to prove that the set of algebraic numbers is countable per se (though if there's an error in my proof please let me know), but rather how would one prove it using the given hint? I struggled for a while trying to figure it out that way before I gave up and tried my above approach.

 

[matt grime]

You have to use the hint to partition the algebraic numbers into countably many finite sets. Or rather partition the set of polynomials into countably many finite sets (which is strictly different, but implies the result).

So, what should I let B_N be (suggestively using the notation of N as in your post).

 

[JohnDuck]

I think I see the gist of it. So, for example, B_{2} would be the set of all polynomials such that n + |a_{0}| +...+ |a_{n}| = 2. Since all the terms are positive and at least one coefficient is nonzero, 2-n must be an integer greater than or equal to 1 and less than 2 (which only leaves 1, which further implies n equals 1). Only two equations satisfy this, namely -x = 0 and x = 0. Since each such B_{n} has a finite number of elements, their union as n ranges through the natural numbers is countable.