Finite But Unbounded “Irrationals”

Suppose we repeat the arguments for a sequence of n digits that are finite but unbounded in n. Is the size of this set of unbounded “irrationals” aleph-one? The answer is no, the size of these irrationals is still aleph-zero. You can discover that it isn’t aleph-one by simply trying to prove that is is using the diagonal argument. For any n the diagonal number has more digits than n and hence isn’t included in the table of irrationals of size n. Thus the diagonal proof fails.

Consider the sets Sn of all “irrationals” on n digits, i.e. Sn is the set of sequences of length n. It is obvious that each set has a finite and countable number of elements. Now consider the set S, which is the union of all of the sets S_n. This is clearly countable as the union of countable sets is always countable and it is infinite – it is aleph-zero in size. You can convert this loose argument into something more precise. You can also prove it by giving an enumeration based on listing the contents of each set in order n. You have to have the set S_∞, i.e. the set of infinite sequences of digits to get to aleph-one.

Enumerations

To see this more clearly you only have to think a little about iteration or enumeration. This section considers this mathematics from a programmer’s viewpoint.
Put simply, anything you can count out is enumerable.

Integers are enumerable - just write a for loop.

for i=0 to 10
 display i
next i

which enumerates the integers 0 to 10. 

Even an infinite number of integers is enumerable, it’s just the for loop would take forever to complete:

for i=0 to infinity
 display i
next i

OK, the loop would never end. but if you wait long enough you will see any integer you care to pick displayed. In this sense, the integers, all of them, are enumerable. The point is that for any particular integer you select the wait is finite.

When it comes to enumerating infinity, the state of getting to whatever item we are interested in if we wait long enough is the best we can hope for. An infinite enumeration cannot be expected to end.

The next question is are the rationals enumerable? At first look the answer seems to be no because of the following little problem. Suppose you start your for loop at 0. The next integer is 1 but what is the next rational? The answer is that there isn't one. You can get as close as you like to zero by making the fraction smaller and smaller – 1/10, 1/100, 1/1000 and so on. There is no next fraction (technically the fractions are "dense") and this seems to make writing a for loop to list them impossible.

However, this isn't quite the point. We don't need to enumerate the fractions in any particular order we just need to make sure that as long as the loop keeps going every rational number will eventually be constructed. So what about:

for n=0 to infinity
  for i=n to 0
    display (n-i)/i
  next i
next n

This may seem like a strange transformation but it corresponds to the “zig zag” enumeration of the rationals given earlier:

You can see that n is the column number. When n is 4, say, we need to enumerate (4,0), (3,1), (2,2), (1,3) and (0,4) and you should be able to confirm that this is what the nested for loops do. Also ignore the fact that we are listing improper rationals of the form (a/0) - you cannot divide by zero.

You should be able to see that if you wait long enough every fraction will eventually be displayed and in addition all of the possible combinations of (a,b) will eventually be produced.

We can agree that even an infinite set is enumerable as long as you are guaranteed to see every element if you wait long enough and so the rationals are enumerable. Notice that we have transformed two infinite loops into a single infinite loop by adopting a zig-zag order. This idea generalizes to n infinite loops, but it is more complicated.

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 fails with the rationals because they can be transformed to a zig-zag order and hence they are enumerable.

However, first we have another problem to solve - how do we write down the irrationals? It is clear that you cannot 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 that can be produced by:

for i=0 to infinity
   display the ith digit of √2 
next i

You should probably begin to expect something different given that now each number is itself an enumerable sequence of digits where integers and rational are simply enumerable as a set.

What about the entire set of irrational numbers – is it enumerable? 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. 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. It’s 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 forever - but a pair of nested infinite loops is 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. However, this isn't about proof, it's about seeing why an infinite sequence of infinite sequences is different from just an infinite sequence and you can derive Cantor’s diagonal argument from it. Now let’s return to the alephs.