In my former column "Hamlet is a big number", I classified numbers into six categories, based on how large theese were: counting numbers, statistical numbers, scientific numbers, literary numbers, inconceivable numbers, and indescribable numbers. This classification measures how big the numbers are. It does not say how complicated they are. For example, googolplex, defined as:
is a huge number; in fact, it is inconceivable, because it is greater than 10 to the 20 billionth power and hence most numbers near a googolplex can't be written down since it would take more than a lifetime to do it in. However, googolplex itself, although it is huge, is simple: in fact, only seven symbols are required to state it. Count them: three 1s and four 0s. Of course the definintion of exponentiation should go in here. But still, googolplex is a simple number. So which numbers are simple and which are complicated?
To tell you how much a number is, I have to state somehow a rule for determining it. For example, for 570,000,000,000, I could tell you to multiply 10 by itself 10 times, then multiply that by 57. I also need to tell you what 10 and 57 are. Computer languages such as Basic and C++ are well built for describing numbers this way. For example, a Basic way of building the number 57 could be
This algorithm has 47 symbols, counting each of the words as one. So in a sense, 57 has complexity 47. So in general, I shall say that the complexity of a number is the number of symbols used to describe it in some language.
So what does this mean as far as complexity of the numbers we encounter are concerned? The same six categories can be used for these complexities: counting, statistical, scientific, literary, inconceivable, and indescribable. The categories now represent the length of the algorithm or procedure used to describe it. In addition there is one more category beyond these even, which I shall call Ultimately Indescribable. To review my six categories, they are:
We find that just about all the numbers we use in everyday work and parlance, including even those used by mathematicians, are countably complicated. That is, they require 1,000 or less symbols to describe it. Think about it. The number 281,421,906 takes only 9 symbols to describe it; maybe a little more if done formally in a programming language. (It is the 2000 population of the United States of America). A googol takes only five symbols to describe it, and a googolplex only about seven. Even Graham's Number, inconceivably huge as it is, takes only a page of print to describe it. All these numbers are in the simplest category: countably complex. Even irrational numbers are countably complex. The square root of 2 takes only two symbols: the 2 and a square root sign. Pi takes only the number of symbols needed to describe the alternating sum of the odd reciprocals multiplied by 4. All of these numbers are countably complicated.
It follows then that even statistically complicated numbers are hard to describe. Any number can be described by its digits. Hence a statistically complicated number must have at least 1,000 digits. If you select 1,200 random digits and string them out to form a number in base 10, that number would be statistically complicated, for I don't think there would be any simpler way of describing it other than to enumerate its digits. So statistically complicated numbers at the minimum are already literary numbers. Many literary numbers are indeed statistically complex; perhaps Hamlet is, although the non-random aspects of Elizabethan text and the suggestions made by the text that are not in the text may make it simpler than it looks. At the maximum, statistically complicated numbers go way above everything else into the indescribable numbers, for some of these require a quadrillion symbols to state. Further, there are numbers between 0 and 10 that are just as complicated. Select one of these complicated numbers, then in its decimal representation put a decimal point between the first and second digits. The resulting number, between 1 and 10, is statistically complicated. This means that complicated numbers not only are way out there, but are right here amongst us in the realm of the counting numbers.
Following the statistically complicated numbers are the scientifically complicated numbers. All of these numbers are indescribable! They require at least a quadrillion symbols to describe, and none of us will ever be able to do it. If by some heroic means someone is able to describe one of these numbers, it is no longer indescribable any more and no longer scientifically complicated. So naturally I can't give you any examples of statistically complicated numbers.
But that's not all. After these come literarily complicated numbers, inconceivably complicated numbers, and indescribably complicated numbers. The number of symbols in an indescribably complicated number is itself a number so huge that none of us will ever be able to describe it. They are way out there on the number line. But they are also amongst us too, because we can reduce them to below 10 by dividing by an appropriately huge number. Yes, between 2 and 3, for instance, there are many indescribably comoplicated numbers.
But that isn't all.There are some numbers so complicated that they can't even be described by indescribably complicated algorithms. And further, these numbers are not way out there in the integers. They are right here, between 0 and 1 even.
The reason why these numbers, which I shall call Ultimately Indescribable, exist was made clear by Georg Cantor in the 19th century. The reason why they exist is that I have described numbers that can be described by a procedure, even if the procedure is an indescribable number of symbols long, and so we can't begin to understand how much the number is. All of the classes I have described so far, from countably complicated to indescribably complicated, nevertheless can be described by a procedure of some sort. And indeed, this is the only way we can understand a number. I have to tell you how to compute it. If I say 157, then the procedure you understand is probably something like 10*10*1+5*10+7, where 10, 5, 7, addition and multiplication are procedures you learned in elementary school; for example, 5 = 1+1+1+1+1. The same holds if I say 10 to the googolplex power, for by that you understand that you take a hundred, raise 10 to that power, raise 10 to that power and raise 10 to that power. There isn't any way I can describe a number to you unless there is a procedure for describing it.
But how many procedures are there? Procedures consist of symbols from some finite alphabet; say A-Z, 0-9, +, -, *, /, and perhaps some others such as parentheses. There are only a finite number of these. So there is only a finite number of procedures using just one letter. There is only a finite number using just two letters, a finite number using three letters, and so forth. So line them up in a string listing the one-letter descriptions first, then the two-letter descriptions and so forth. It is possible to give an integer to each of these descriptions since there are only a finite number in each. There are an infinity of possible procedure lengths, but there are only a finite number in each case, so this is possible. Since we have just paired up the procedures with the integers in a one-to-one fashion, we say that the procedures are a countable set. Even though there are an infinity of them, nevertheless, one can count them, 0, 1, 2, 3, ... and cover all procedures. Therefore the totallty of all countably complicated to indescribably complicated numbers that there are can be paired one to one with the integers, so these are a countable set as well. If these are the only numbers there are, then there are only a countable infinity of numbers. So the question is: is the set of all real numbers on the real number line countable?
No. This is what Cantor showed. Here is why. Suppose there were such a list of real numbers. Then there would be a list of real numbers between 0 and 1. Maybe the list looks like:
This list supposedly contains all real numbers. But does it? Let's color-code the diagonal:
Now I shall describe another real number. I could say "0.1100804..." by going down the diagonal, but instead I'm going to be a little perverse about this. I'm going to change the digit every time. Since the first digit is 1, I am going to use a 2 instead. Since the second one is a 1, I will use a 2 there as well. The third digit will be a 1, and so forth, hopping from the diagonal digit to the next digit. If I encounter a 9, I will change it to a 0. I then create the number z = 0.2211915... . OK, this is a real number. So where is it in my list? Supposedly this list contains all the real numbers.
Well, it can't be the first number on the list. Why not? Because it differs in the first digit. Why does it differ in the first digit? Because I created z that way. I selected it so that the first digit of the first number on the list would not be the same as the first digit of z. Well, can it be the second number? No, because I chose its second digit to be different from the second digit of the second number on the list. The second digit of z is 2. The second digit of the second number of the list is 1. I made it that way.
Then can it be the third number? No, becuase they differ at the third decimal place, for the reasons I just described. In the same way, it can't be the fourth number or the fifth number and so forth. Can z be the googolplexth number? No. They differ in the googolplexth digit. And so forth.
In other words, z is not any of the numbers on the list! Supposedly this was a list of all numbers yet we have found one that is not on the list. Now if the list of real numbers was the one I described earlier that listed the results of all the procedures for describing numbers, then z can't be described by any procedure, not even one that is indescribably complicated. z is one of a brand new set of numbers, those that can't be described by any algorithm. I call these numbers Ultimately Indescribable.
No you can't fix the argument by sticking z at the beginning of the list. If you do you get this:
Now I will select a new z by the same procedure: z = 0.3532151... This z is not on the new list, by the same reasons as before. The point is that the proof applies to all purported lists of real numbers, not just the piece of a specific one I just mentioned.
So now we have a set of really way-out numbers called Ultimately Indescribable. So where are they? Are they way out beyond the indescribable numbers, beyond the indescribably complicated numbers, beyond all of that? No. That is because these numbers are integers, and there are only a countable number of them. No. The Ultimately Indescribable numbers are among us. They are between 0 and 1, they are between 1 and 2, and so forth. There are an uncountable number of Ultimately Indescribable numbers that begin with 3.14159265358... , and no, pi is not among them because it is countably complicated. I can't describe any to you, for I can only do it with a procedure. I can say only roughly where they are. Everywhere.
We therefore went way out to find indescribably complicated numbers, only to find that the only place we can find the Ultimately Indescribable ones are right here at home, amongst the simplest counting numbers. There may be a religious analogue to us. Many religions believe that God is not way out there; It is among us all.
2004 January 18
Back to Main Page