# Prove algebraic numbers are countable

1. May 29, 2007

### JohnDuck

1. The problem statement, all variables and given/known data
"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$$.

2. Relevant equations
See above.

3. 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.

Last edited: May 29, 2007
2. May 30, 2007

### 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).

3. May 30, 2007

### 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.