Transcendental numbers

How many real numbers are there? How many algebraic numbers are there?

 

All algebraic numbers, by definition, satisfy some polynomial equation with integer coefficients. Since a polynomial of degree n has exactly n coefficients, there are a countable number of such polynomials. Every possible such polynomial has at most n distinct zeros so there are a countable number of solutions to all possible nth degree polynomials. Since there are a countable number of possible degrees, the set of all possible solutions to all polynomials with integer coefficients, i.e. the set of all algebraic numbers, is countable. The set of all real numbers is uncountable so the set of all real numbers that are not algebraic, the set of all transcendental numbers, is uncountable.

 

Here is an outline of the proof

Consider this definition of an algebraic number:

Let A denote the set of algebraic numbers. Then z is in A IFF z is a root of a ploynomial with integer coefficients (sometimes stated with rational coefficients, but this is equivalent).

That is z is in A IFF there exists integers a0,a1,a2,...,an not all zero such that the polynomial P(z):=sum(ak*z^k, k=0..n)=0.

You can prove A is countably infinite by:first defining the height of a polynomial as the sum of the absolute values of its coefficients and its degree, e.g., |P(z)|=|a0|+|a1|+...+|an|+n for the above polynomial.

Then prove that there are finitely many polynomials of a given height, and that each such polynomial has finitely many roots (use the fundamental theorem of algebra for the second part).
Let the (finite) union of the sets of the roots of polynomials of height m be denoted by Hm. Then A is the (countable) union of Hm over all positive integers m (why?) Therefore A is countable (why?)

The set of transdental numbers must then be uncountable (why?)

 

Do you know this theorem: If A and B are countable sets then AxB (Cartesian product: ordered pairs where first member is in A and second in B) is countable. To prove that, imagine that you make a table by listing all members of A horizontally (you can do that because A is countable) and listing all members of b vertically (you can do that because B is countable). The pair (a,b) is written in the column headed a along the top and the row headed b on the left. Now you can go through that table "diagonally"- you may have seen proofs that the set of all rational numbers is countable done that way.

The set of all pairs (a,b) where a and b are both integers is countable because it is NxN and N is countable. Of course, we can identify the linear polynomial a+ bx with (a,b).

It is then easy to show that the Cartesian product of three countable sets AxBxC is countable by thinking of this as (AxB)xC. AxB is the product of two countable sets and so is countable, then (AxB)xC is the product of two countable sets and so is countable.
But we can identify the polynomial a+ bx+ cx² with (a, b, c).

In general, the Cartesian product of any finite number of countable sets is countable and we can identify a+ bx+ cx²+ ...+ zxⁿ with the ordered n-tuple (a, b, c, ..., z) showing that the set of all possible nth degree polynomials with integer coefficients is countable.