The algebraic numbers are countable

By definition an algebraic number is a complex number which satisfies some polynomial a_0+a_1x+\cdots a_nx^n\in\mathbb{Z}[x]. Every rational number m/n is algebraic as m/n satisfies nx-m. Further irrational numbers can also be algebraic, \sqrt{n},n\in\mathbb{N} clearly satisfies x^2-n. Similarly purely imaginary numbers can be algebraic: i obviously satisfies x^2+1.

Just as algebraic numbers are called so because they lie within the range of the “classical algebra” (by which we understand manipulation of the integers) to be “described entirely”, a non-algebraic number is called transcendental because one needs to transcend this “algebra” to describe it. There are only a few mathematically significant numbers which are known to be transcendental. For 2500 years a debate ranged as to \pi was transcendental or not, before the question was settled in the affirmative by Lindemann in 1882. Similarly e is transcendental. (We do not know whether \pi+e is transcendental or not).

Surprisingly, even though the transcendental numbers seem fewer then the algebraic numbers they actually exist in greater abundance. In fact, almost every real number is transcendental. This is because the set of algebraic numbers is countable and hence has Lebesgue measure zero. Our aim in this post is to formally prove the countable nature of the algebraic numbers.

Theorem: Let A be the set of all algebraic numbers. Then A is countable.

Proof: We define a height h of a polynomial a_0+a_1x+\cdots a_nx^n\in\mathbb{Z}[x] as h=n+\sum_{i=0}^n|a_i|. Clearly for a fixed h there are only finitely many choices for n and a_i and so there are only finitely many polynomials of fixed height.

Now we make a list of all the algebraic numbers in the following way: Consider any height h\in\mathbb{N} and for all the finitely many polynomials of this height, write down all the finitely many roots of these polynomials in the list. Keep repeating for all possible heights. It is clear that no algebraic number will be missed out in this list. This proves that A is countable.\Box

Advertisements

Leave a comment

Filed under Algebra, Real Analysis

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s