Tag Archives: real numbers

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

Real numbers are uncountable

One of the slickest proofs of all time is using Georg Cantor‘s 1891 diagonal argument in proving that the real numbers \mathbb{R}  constitute an uncountable set, that is, they cannot be put in a bijective correspondence with \mathbb{N}. Strictly speaking, Cantor original paper only proved that the set of all 0,1-sequences is uncountable. However since it is easy to argue that the set of all such sequences and \mathbb{R} have the same cardinality, indirectly we get a proof for the uncountable nature of the reals. Moreover, the argument given by Cantor in his proof can be easily modified to give a direct proof for the uncountability of the reals. This is what we do presently.

Theorem: \mathbb{R} is uncountable.

Proof: We will accept that every real number x has a decimal expansion, x=N.x_1x_2\cdots and it is uniquely determined by x if one agrees never to terminate the expansion with an infinite string of 9‘s. The proof is based on contradiction, and so we suppose that \mathbb{R} is not uncountable. Then it must be that \mathbb{R} is countable and we can make a list of all the elements of \mathbb{R} along with their decimal expansion as follows:

x_1=N_1.x_{11}x_{12}x_{13}\cdots\\x_2=N_2.x_{21}x_{22}x_{23}\cdots\\x_3=N_3.x_{31}x_{32}x_{33}\cdots\\\vdots

We now consider the real number 0.y_1y_2y_3\cdots which is defined by y_i=1 if x_{ii}\ne 1 and y_i=2 otherwise. It is clear that this number differs from every x_i in the list in at least the i‘th position. Hence this list is incomplete, a contradiction.\Box

Leave a comment

Filed under Real Analysis, Set theory