You may have heard a rumor that infinity comes in a number of different types. Get to the bottom of the theory and dispel misconceptions surrounding aleph-zero and all that, with a programmer's view of the transfinite numbers.

{loadposition CONTENTSTheory}

Aleph Zero and all that

There are different orders of infinity. The usual infinity, or the smallest infinity if you can cope with this terminology, is usually called aleph-0, (aleph-zero or aleph-null) and is written

You can guess that, as this is aleph-zero and not just Aleph, there are others in the series and aleph-1, aleph-2 and so on are all different orders of infinity, and yes there are, probably an aleph-0 of them.

What is this all about?

Surely there is just infinity and that's that?

The set of different orders of infinity or the "transfinite" numbers are an important idea that plays a role in computer science and the way we think about algorithms in general. Even if you are not going to specialise in computer science and complexity theory, it is part of your intellectual growth to understand one of the deepest and most profound theories of the late 19th and early 20th centuries.

The theory of transfinite numbers was constructed by German mathematician, Georg Cantor (1845-1918)

Unbounded v Infinite

Programmers meet infinity sooner and more often than the average person. OK, mathematicians meet it all the time but perhaps not in the reality of an infinite loop.

Question: How long does an infinite loop last?

Answer: as long as you like.

This highlights a really important idea. We really don't have an infinite loop, what we have is a finite but unbounded loop.

Finite but unbounded is an interesting concept that deserves to be better known. Something that is finite but unbounded is on its way to being infinite but it isn't actually there yet.

Consider the difference between the following two sets:

U= the set of counting numbers less than n

N = the set of natural numbers i.e. 0,1,2,3..

Set U is finite for any n but it is unbounded in that it can be as big as you like depending on n. On the other hand, N is the real thing - it is an infinite set.

It is the difference between someone offering you a very big stick to hold - maybe one that reaches the orbit of the moon, the sun or perhaps the nearest star, and a stick that is really infinitely long.

A stick that is finite but "as big as you like" is similar to the sort of sticks that you know. For one thing it has an end point. An infinite stick doesn't have an end point - so how can you point it at something? 

A bigger stick is just that, but an infinite stick is something else - something new.

The same arguments hold for U and N. The set U always has a largest member but N has no largest member. Infinity is different from finite but unbounded. 

When you write an infinite loop you are really just writing a finite but unbounded loop - someday it will stop.

In the same way, it is a subtle point that the paper tape used by a Turing machine isn't infinite but it is unbounded. You can always make some more paper and add it to the existing tape - it can be as long as is needed.

Often finite but unbounded is all we need to prove theorems or test ideas and it avoids difficulties. For example, a finite but unbounded tape does have a last item, but an infinite tape doesn't. A Turing machine working with tape that doesn't a have an end is more than just a mechanical problem.

Many of the properties of a Turing machine depend on the tape being unbounded. For example, the halting problem says that you can't create a Turing machine that can read the tape that describes another Turing machine and decide if it halts or not. This is a well known limitation but notice that if you can limit the size of the Turing machine that is being tested you can write a program that works out if it all Turing machines up to this size halts or not. The impossibility prove depends on the size of the machine being unbounded.

There is a very real difference between an unbounded loop and an infinite loop. Consider, for example, two nested for loops. If the outer loop is infinite then everything is more or less OK. The inner loop terminates and the outer continues.

For I=1 To Infinity
 For J=1 To 5
  print(i,j)
 Next J
Next I


prints  1,1 1,2 1,3 1,4 1,5 2,1 2,2 2,3 2,4 and so on...

Both loops make progress and in this sense the program sort of works.

If the inner loop is an infinite for loop then, just like an infinite tape, it never ends and so the outer loop never gets to move on.

For I=1 To Infinity
 For J=1 To Infinity
  print(i,j)
 Next J
Next I

prints  1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 and so on..

The outer loop never moves on and in this sense the program's logic is completely broken.

Programming abhors nested infinite loops.

So now we move to the truly infinite. not just things that are unbounded in the previous sense  of "as big as you like".

Cantor's work on the infinite is said to have driven him mad, but this is another misconception.

This theory is perfectly rational - and, as well shall see, irrational.

The problem of size

The basic idea of the size of something is that if two sets are the same size then we can put them into one to one correspondence. Clearly if this is the case then the two sets are of the same size as there can't be any "things" hiding in one set that make it bigger than the other set.

This definition seems innocent enough, and it is, but you have to trust it and the conclusions you reach when you use it to compare infinite sets.

For example, suppose you take the set Z of all integers  then this is clearly an infinite set. Now take the set O of all the odd  integers - this set clearly has half the number of things in it.

But wait - if you set up the 1:1 correspondence between O and Z such that each n in O is associated with 2n in Z  we have to conclude that O and Z have the same number of elements - they are both sets with an infinity of elements.

This is the source of the reasonably well known illustration featuring Hotel Hilbert.

The hotel has an infinite number of rooms and on this night they are all full when a tour bus arrives. The passengers are accommodated by the simple rule that the existing guests in room n move to room 2n - thus clearing all of the odd numbered rooms and making enough space for an infinity of new guests.

If you would like to see a little more of Hotel Hilbert then try the short video made by the Open University:

Interestingly from the algorithmic point of view, you can set that the    n->2n move would clear enough rooms for any finite size coach load in a finite amount of time, but if the coach held its own infinity of new guests then the time to clear the space needed would also be infinite.

In short, you can add or subtract any number from an infinite set and you still have an infinite number, even if the number added or subtracted is infinite.

My favorite expression of this fact is:

Aleph-null bottles of beer on the wall,
Aleph-null bottles of beer,
You take one down, and pass it around,
Aleph-null bottles of beer on the wall.

<ASIN:0691024472>

<ASIN:014014739X>

<ASIN:0486600459>