San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The Cardinality of the Algebraic Numbers

Algebraic Numbers

Algebraic numbers are numbers which are solutions to polynomial equations with integer coefficients, Such a number is √2, which is a solution to x2-2 = 0. Integers and rational numbers are special cases of algebraic numbers. Although the set of algebraic numbers includes many irrational numbers like √2, it does not contain all irrational numbers. For example, the constant π is not an algebraic number. It is called a transcendental number; i.e., a real number which is not an algebraic number. There are only a few familiar transcendental numbers. The base of the natural logarithms, e=2.71828182859045..., is another familiar transcendental number.

It might seem that there are many more algebraic numbers than transcendental numbers, but actually the reverse is the case. There is a higher order of infinity more transcendental numbers than algebraic numbers. The cardinality of the algebraic numbers is ℵ0, the same as the natural numbers (nonnegative integers), integers and rational numbers. This means that the cardinality of the set of transcendental numbers is the same as that of the set of real numbers, the order of the continuum.

To prove the above assertions let us first consider the set of all polynomials with integer coefficients. This is just as general as considering polynomials with rational number coefficients because one can multiply by the denominators of rational coefficients to get integer coefficients. The set of all integer coefficient polynomials is the union of the set of all such linear equations, quadratic equations, cubic equations and so on.

The cardinality of the set of all integer coefficient linear equations is (Z-{0})×Z. The leading coefficient of a polynomial should not be zero. The cardinality of the set of all linear equations is


0×ℵ0=ℵ0
 

Likewise the cardinality of the set of all integer-coefficient quadratic equations is ℵ0×ℵ0×ℵ0 = ℵ0. Similarly the cardinality of all n-th degree polynomials is ℵ0.

Any n-th degree polynomial has at most n distinct roots. Therefore the cardinality of the set of roots of all n-th degree polynomials is at most n×ℵ0=ℵ0. Thus the cardinality of the set of roots to all integer-coefficient polynomials is at most


0+ℵ0+ℵ0+... =
0×ℵ0 = ℵ0
 

Remarkably the set of all such roots is countable.

If the coefficients are allowed to be roots of integer-coefficient polynomials the cardinality of the set of roots is still ℵ0. Thus by expanding the set of coefficients we never get a set that has a cardinality greater than ℵ0

Although algebraic numbers are usually defined as the roots of integer coefficient polynomials the concept can obviously be generalized through a recursive definition. Let S1 be the roots of all integer coefficient polynomials. Let Sm be the set of roots of all polynomials which have coefficients belonging to the set Sm-1. For each m it is true that Sm-1 ⊂ Sm. The generalized algebraic numbers are members of the set which is the limit of Sm as m goes to infinity. That set can be appropriately denoted as S.

The denumerable cardinality of the generalized algebraic numbers is established by a process similar to that used in establishing the denumerability of the rational numbers. Let Am = Sm - Sm-1 and A1 = S1.

The cardinality of S1 has previously been established as ℵ0, and likewise the roots of polynomials with coefficients from a denumerable set is denumerable. The set Am, being a subset of a denumerable set, is also denumerable. Each Am can be put in an order sequence, say:


(A1,1, A1,2, A1,3...)
(A2,1, A2,2, A2,3...)
(A3,1, A3,2, A3,3...)
...........................
...........................
...........................

 

Clearly the Axiom of Choice is needed in this construction.

Now consider the ordering


(A1,1, A1,2, A1,3, A3,1, A2,2, A3,1, ....)
 

Every element of the sets is picked up in this sequence and thus ∪Am = S is put into a one-to-one correspondence with the natural numbers. The proof must allow for the possibility that some Am might be finite or even empty. This constitutes no problem because the sequence can pick up the next existing element in the pattern.

Note that the generalized algebraic number must be defined recursively. A circular definition that a generalized algebraic number is a root of a poynomial with generalized algebraic number coefficients would lead to the argument that π is a generalized algebraic number because it is the solution to the linear equation x - π = 0. Such a definition leads only to the real numbers.

Let us now consider a more general and detailed analysis of the above construction. Let the set of coefficients be C and its cardinality #C. The set C might be an arbitrarily restricted set, such as integers less than 216. Such limitations arise in the computer technology.

The cardinality of the set of such n-th degree polynomials is less than or equal to the cardinality of {C-{0}}×C×...×C; i.e., (#C-1)(#C)n-1. The cardinality of the set of roots of n-th degree polynomials is less than or equal to n(#C-1)(#C)n-1. Thus the cardinality of the set of roots to all finite polynomials of degree less than or equal to N is:


Σn=1N[n(#C-1)(#C)n-1] =
(#C-1)Σn=1N[n(#C)n-1]
 

Note that the sum of a geometric series has the formula


Σn=1Nxn = (xN+1−1)/(x−1)
and its derivative is
Σn=1Nnxn-1 = (N+1)xN/(x−1) − (xN+1−1)/(x−1)2
 

Thus


Σn=1N[n(#C-1)(#C)n-1] =
(#C-1)[(N+1)(#C)N/(#C-1) − ((#C)N+1−1)/(#C-1)2]
which reduces to
(N+1)(#C)N − [(#C)N+1−1)/(#C-1)]
 

This is on the order of N(#C)N.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins