Monday, October 8, 2012

Not enough names for numbers

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

Napier's constant, Pi, Planck constant, golden ratio, etc. We have given names to many special numbers. However, there are far many numbers than our human language can handle. It is not a philosophical statement, it is a true mathematical theorem which is surprisingly simple to prove.

A language consists of phrases which are finite sequences of a finite set of symbols. English phrases, for example, are finite sequences of 'a' to 'z' and the empty space. If we assign an ordering of the symbols, then we also assign an lexographical order of phrases. If we assign 'a'<'b'<...<'z'<' ', we will have 'ab cd'<'acbde'<'a bac'. In other words, all possible phrases in a language can be listed.

We are now going to prove that the set of all real numbers between 0 and 1 cannot be listed, and hence there are far more numbers than possible words:

Suppose on the contrary, the set of all real numbers between 0 and 1 can be listed as follows

0.α11α12α13α14α15
0.α21α22α23α24α25
0.α31α32α33α34α35
0.α41α42α43α44α45
……………

Now, construct a real number 0.β1β2β3β4β5… such that βj≠αjj, 0 and 9.

Under this special construction, the new number is different from the j-th number in the list, as they have different j-th digits. (Note that two numbers with different digits can be the same, e.g. 0.10000… and 0.09999… but this will not happen in our construction.) Therefore, the new number is not in the list of all real numbers between 0 and 1, which is obviously a contradiction.

The above construction is the famous Cantor's diagonal argument by Georg Cantor (1845-1918).  This seemingly simple technique is indeed rather powerful, it is used in the arguments for Russell's paradox, the first of Gödel's incompleteness theorems, and Turing's answer to the Entscheidungsproblem.