Enumerating the irrationals

Fractions and hence the rationals are enumerable.

The next question is - are the irrationals enumerable?

At first sight it seems not, by the same argument that there is no "next" irrational number but as we have seen this argument failed with the rationals because they are enumerable.

However first we have another problem to solve - how do we write down the irrationals? 

It is clear that you can write them down as anything like a/b so how do you do it?

After lots of attempts at trying to find a way of representing irrational numbers the simplest way of doing the job is to say that an irrational number is represented exactly by an infinite sequence of digits - for example

3.14159...

where the ... means "goes on for ever".

You can see that a single irrational number is composed of an  enumerable sequence of digits. For example

for i=0 to infinity
   display the ith digit
   of the square root of two
next i

Now what about the entire set of irrational numbers?

This is quite a different problem because now you have a nested set of for loops that both go on to infinity

for i=0 to infinity
 for j=0 to infinity
  display jth digit of the
  ith irrational
 next j
next i

The problem here is that you never get to the end of the inner loop so the outer loop never steps on by one. 

In other words, no matter what the logic of the program looks like, it is, in fact, functionally equivalent to:

i=0 
 for j=0 to infinity
  display jth digit of the 
  ith irrational
 next j


The original nested loops only appear to be an enumeration because they look like the finite case. In fact the program only ever enumerates the first irrational number you gave it.

Its quite a different sort of abstraction to the enumeration of the rationals and while it isn't a proof that you can't do it - it does suggest what the problem might be.

As the inner loop never finishes the second loop never moves on to another value of i and there are huge areas of the program that are logically reachable but are never reached because of the infinite inner loop. 

It is as if you can have one infinite for loop and see results, all the results if you wait long enough - but a pair of nested infinite loops is something non-computable because there are results you will never see no matter how long you wait.

The point is that you can't enumerate a sequence of infinite sequences. You never finish enumerating the first one so you never get to the second...

As already stated this isn't a proof but you can construct a proof out of it to show that there is no effective enumeration of the irrationals.

But this isn't about proof, it's about seeing why an infinite sequence of infinite sequences is different from just an infinite sequence.

Cantor's diagonal argument

If you do want a proof then the standard one is called "Cantor's diagonal argument" and its an argument by contradiction as are most of the arguments in this area of computer science.

Suppose you do have a complete enumeration of the irrationals and you decided to print out a table of the first few digits of the first few numbers.

For example a 3x3 section of the table might be :

 .122...
 .348...
 .567...

Now construct a new irrational number by taking the first digit to be different from the first digit of the first irrational number 3 say, the second digit to be different from the second digit of the second irrational number 6 say and finally its third digit to be different to the third digit of the third number 4 say.

That is construct a new number by taking each digit in the diagonal and creating a number that uses a different digit in that location:

 .122...
 .348...
 .567...

and our number is different from .147 e.g. .364

Now we have a new irrational number .364 and you are guaranteed that it is not in the table so far because it differs from the nth enumerated irrational in the nth digit.

So what you may say this is just an irrational number that we haven't generated yet. Let's make the table bigger by enumerating some more irrational numbers till we find the constructed value. Unfortunately at this point I can use the same trick to construct another number that isn't in the table.

No matter how big you make the table I can always find a number that isn't in it and so your compete enumeration of the irrationals cannot be done.

So looking at what can and cannot be enumerated has revealed some interesting things about the way we can work with infinity but what has this to do with non-computable numbers?

<ASIN:0285635948>

<ASIN:0691024472>