Prove That The Set Of All Algebraic Numbers Is Countable

Counting the Roots of Integer Polynomials

The first time I tried to explain this to a study group, someone insisted that because every algebraic number comes from a different equation, there must be too many to count. That intuition feels right until you actually look at how the equations stack up. A non-zero polynomial with integer coefficients is completely determined by its finite list of coefficients. Even if you allow arbitrarily high degree, that list is always a finite sequence of integers. I remember hitting a snag while building a small script to enumerate low-degree algebraic numbers. I sorted polynomials by degree and then by the sum of the absolute values of the coefficients, but the output kept repeating the same number under different factors. For example, 2 appears as a root of both x² 2 and x³ 2x. The fix was simple once I stopped trying to assign each algebraic number to a unique parent polynomial. You only need one polynomial per number, not a perfect one-to-one matching between numbers and equations.

Prove That The Set Of All Algebraic Numbers Is Countable

Here is the argument without the theatrical packaging. Let A be the set of all algebraic numbers. By definition, A if and only if there exists a polynomial P(x) = a_n x^n + … + a_1 x + a_0 with integer coefficients, not all zero, such that P() = 0. Because the coefficients are integers, each such polynomial belongs to the union over all n 0 of ℤ^{n+1}. Each ℤ^{n+1} is countable, and a countable union of countable sets is countable, so the set of all non-zero integer polynomials is countable. Write that countable family as {P_1, P_2, P_3, …}. For each k, let R_k be the set of complex roots of P_k. The Fundamental Theorem of Algebra guarantees that R_k is finite, with at most deg(P_k) elements. Then A = _{k=1}^ R_k. A countable union of finite sets is countable, so A is countable. To see that A is actually infinite, note that every rational number p/q is a root of the linear polynomial qx p. Since ℚ is infinite, A is infinite. Therefore A is countably infinite.

There is a small but useful refinement if you want an explicit enumeration instead of an existence proof. Assign each non-zero polynomial its height H(P) = max{n, |a_0|, |a_1|, …, |a_n|}. For each positive integer H, there are only finitely many integer polynomials with height H, so you can list all their roots in order of increasing height, then by degree, then by coefficient lexicographically. If you encounter the same root from different polynomials, just skip the duplicates. That produces a single infinite sequence containing every algebraic number exactly once. The thing people usually miss is that this proof does not depend on any special properties of 2 or other familiar surds. It works for every root of every integer polynomial, including numbers defined by massive high-degree equations. What fails if you change the coefficient ring to something uncountable, like ℝ[x]. Then you instantly get uncountably many constant polynomials, and the whole argument collapses. The countability comes entirely from the coefficients coming from a countable set. Another practical limit is that this method tells you nothing about which numbers are algebraic beyond the fact that they appear somewhere in the list. Deciding whether a specific real number given by a decimal expansion or a geometric construction is algebraic can be much harder than the counting argument suggests. The proof is clean, but it is not a decision procedure.

So the conclusion is straightforward. The algebraic numbers form a countably infinite subset of the complex numbers, and the standard way to show that is to view them as the roots of a countable family of integer polynomials, each contributing only finitely many points.