Friday, September 18, 2009

Indescribable numbers

This post is an attempt to explain what the term indescribable number means. Unfortunately, while this is a relatively well know term I frequently see it being misused. To understand it, we must firstly look on the proof that such numbers exist. It is a rather basic proof from set theory. What we need to do is to define two sets:

A={all the mathematical symbols and all the letters}
B={finite words in A}

Now, it is obvious that A is finite. B is not finite but it is only countably infinite (this is the smallest infinity). Therefore, B is smaller than the set of all numbers - R. Since all the possible descriptions are in B we conclude that there are numbers in R that cannot be described at all. Moreover, if you take away all the numbers that can be described the size of R will not change (this is a basic theorem in set theory). From this we can conclude that in fact most numbers are indescribable. This is a perfectly valid example of nonconstructive proof.

Unfortunately, this simple and short proof (I didn't proof all I said, but it is all just basic theorems of set theory) does little to explain what an indescribable number is. Lets consider some examples. For the first example, look on the following set:

C={words in A shorter than one hundred letters}

It is obvious that C is finite. Therefore there is a maximum number described by C. The next integer number (lets call it Y) is thus "the first integer number that cannot be described in 100 letters". But this description is less then 70 letters long. And this means that this number should be in C. Obviously this is a paradox. We got a number that is both in C and not in C.

Here is another example of a similar problem. It is possible to proof that if you randomly choose a real number the probability of it being an indescribable number is 1. So lets randomly choose a number (since we are choosing only one number we don't need the choice axiom). Naturally we get an indescribable number. Well, lets call this number "indescribable number 1". In the case you didn't notice I just gave a description to an indescribable number.

What really is going on is just an indexing problem. It is important to understand that both B and C are just sets of index numbers. If we have such a set we can use it to index another (in our case the set R). Mathematically, description as it was used in those examples is just a function from B to R (or from C to R). But the way we apply the indexing is arbitrary - we can choose any function we want. Lets first look on the 100 letters case. When we defined the set C what we really defined is the pair (C, f). In this pair f is a description function that for any x in C returns a specific number in R (I suppose that all the words in C describe some number, but you can do without it). Since we cannot define Y without firstly defining (C,f) the word ""the first integer number that cannot be described in 100 letters" is assigned by f to some random number. Then when we got a description for Y, we basically created a new pair (C, g). In this pair g is a new function that agrees with f on all C except for one word - ""the first integer number that cannot be described in 100 letters". To this word it assigns Y. For us this may seem illogical, because we think about meaning of words. But in this proof meaning is not important - the words are just a way to index.

With this in mind, lets consider the second example. In this case the number we choose belongs to a set R\f(B). When we gave it a description all we did was to change f in such a way that now this number belongs to f(B). It is obviously not a problem to do such a change (if we wanted to change the function for an infinite amount of values it might have been a problem, but for one index it is always easy to do).

So, what is an indescribable number? After all, we just saw that it is possible to describe any random number. The answer to this is actually simple. Mathematically it is a number that was not indexed by the function f. In normal language it means that it is a number that wasn't described. Form a normal person point of view this is a weird definition, but mathematically it actually makes a lot of sense. The basic idea is that while we have the option to choose any function f, we can only choose one and we cannot change our choice to another function latter on (this is because we need our language to be consistent). Under this conditions it becomes obvious that both examples are just a misunderstanding of what an indescribable number is. You cannot take a number that is not described and give it a description, because the description is already in use and you can have only one number for one description .
But then, what is the point in saying that such numbers exit? It is after all obvious that there are numbers that are not described as of now. Unfortunately this is not what the theorem is about. The point of this theorem is not to say that there are numbers that we didn't describe. This theorem says that no matter what function f we use there are always numbers that are not in f(B). In other words, there are always will be numbers that we didn't describe even if we used all of B for the purpose of such description.

No comments: