Show that the set of algebraic numbers is countably infinite

Show that the set of algebraic numbers is countably infinite.

Solution

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

Let AA be a countable set, and let BnBn be the set of all n-tuples (a1,...,an)(a1,...,an), where akA,k=1,...,n,akA,k=1,...,n, and the elements a1,...,ana1,...,an need not be distinct. Then BnBn is countable.

So by this theorem, the set of all (k+1)(k+1)-tuples (a0,a1,...,ak)(a0,a1,...,ak) with a00a00 is also countable.

Let this set be represented by ZkZk. For each a aZkaZk consider the polynomial a0zk+a1zk1+...+ak=0a0zk+a1zk1+...+ak=0.

From the fundamental theorem of algebra, we know that there are exactly kk 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 ZksZks, each containing a countable number of (k+1)(k+1)-tuples, each of which corresponds with kk roots of a kk-degree polynomial. So our set of complex roots (call it RR) is a countable union of countable unions of finite sets. This only tells us that RR is at most countable: it is either countable or finite.

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