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.α₁₁α₁₂α₁₃α₁₄α₁₅…
0.α₂₁α₂₂α₂₃α₂₄α₂₅…
0.α₃₁α₃₂α₃₃α₃₄α₃₅…
0.α₄₁α₄₂α₄₃α₄₄α₄₅…
……………

Now, construct a real number 0.β₁β₂β₃β₄β₅… 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.