# Prove that the set of all algebraic numbers is countable

A complex number $z$ is said to be algebraic if there are integers $a_0, ..., a_n$, not all zero, such that
$a_0z^n+a_1z^{n-1}+...+a_{n-1}z+a_n=0$.
Prove that the set of all algebraic numbers is countable.
The Hint is: For every positive integer $N$ there are only finitely many equations with
$n+|a_0|+|a_1|+...+|a_n|=N$.

Here is a proof I have. The problem though, is that I did not use the hint provided in the text, so maybe this proof is invalid or that there is an

Proof:

The set of integers is countable, we have this following theorem:

Let $A$ be a countable set, and let $B_n$ be the set of all n-tuples $(a_1,...,a_n)$, where $a_k \in A, k=1,...,n,$ and the elements $a_1,...,a_n$ need not be distinct. Then $B_n$ is countable.

So by this theorem, the set of all $(k+1)$-tuples $(a_0,a_1,...,a_k)$ with $a_0 \neq 0$ is also countable.

Let this set be represented by $\mathbb Z ^k$. For each a $a \in \mathbb Z ^k$ consider the polynomial $a_0z^k+a_1z^{k-1}+...+a_k=0$.

From the fundamental theorem of algebra, we know that there are exactly $k$ complex roots for this polynomial.

We now have a series of nested sets that encompass every possible root for every possible polynomial with integer coefficients. More specifically, we have a countable number of $\mathbb Z^k s$, each containing a countable number of $(k + 1)$-tuples, each of which corresponds with $k$ roots of a $k$-degree polynomial. So our set of complex roots (call it $R$) is a countable union of countable unions of finite sets. This only tells us that $R$ is at most countable: it is either countable or finite.

To show that $R$ is not finite, consider the roots for $2$-tuples in $\mathbb Z^1$. Each $2$-tuple of the form $(-1, n)$ corresponds with the polynomial $-z + n = 0$ whose solution is $z = n$. There is clearly a unique solution for each $n \in \mathbb Z$, so $R$ is an infinite set. Because $R$ is also at most countable, this proves that $R$ is countable.

Yes, you’re correct; if you want to be more formal, you’re using Cantor-Schroeder-Bernstein in your last step http://en.wikipedia.org/wiki/Cantor-Schroder-Bernstein_theorem , in concluding, from the existence of an injection between the set of all roots and the collection of polynomials and an injection between the pairs ($(1,n)$ and the set of all possible roots, that the collection of roots (i.e., the algebraic numbers) is countably-infinite.