Infinity -- there is nothing bigger? Or is there? It is a surprising but entirely logical conclusion that infinity comes in different sizes but where do we find a bigger infinity? This is what this extract from Chapter 6 of my recent book is all about.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
8. The Algorithm of Choice 
9. Gödel’s Incompleteness Theorem
10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
11. Information Theory 
12. Coding Theory – Splitting the Bit
13. Error Correction 
14. Boolean Logic
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

Once you get over the idea of infinity it doesn't seem so bad. It a number so big that taking any amount away or adding anything to it from it leaves it unchanged. This is all fine but is there just one kind of infinity? As we already know the usual kind, the infinity of the integers is usually called Aleph Zero - does this imply there might be an Aleph One or more?

In book but not in this extract:

• Integers and Rationals
• The Irrationals
• The Number Hierarchy
• Aleph-Zero and All That
• Unbounded Versus Infinite
• Comparing Size

In Search of Aleph-One

Is there an infinity bigger than the infinity of the integers?

At first you might think that the rationals, i.e. numbers like a/b where a and b are integers, form a bigger set - but they don't. It is fairly easy, once you have seen how, to arrange a one-to-one assignment between integers and rational fractions.

If you have two sets A and B then the Cartesian product  A X B of the two sets is the set of all pairs (a,b) with a taken from A and b taken from B.

If A and B are the set of all positive integers you can consider all the pairs (a,b) as the co-ordinates of a point in a grid with integer co-ordinates. 

Now simply start at the origin and traverse the grid in a diagonal pattern assigning a count as you go:

0->(0,0), 1->(1,0), 2->(0,1), 3->(2,0), 4->(1,1)

and so on.

Clearly we have a one-to-one mapping of the integers to the co-ordinate pairs and so the co-ordinate pairs have the same order of infinity as the natural numbers. This also proves that the Cartesian product, i.e. the set of all pairs, of two infinite sets is the same size. 

You can modify the proof slightly to show that the rationals a/b with b not equal to 0 is also just the standard infinity. You can see that in fact using this enumeration we count some rationals more than once.

Basically, if you can discover an algorithm that counts the number of things in a set, then that set is countable and an infinite countable set has order of infinity aleph-zero.

Two questions for you before moving on.

1. Can you write a for loop that enumerates the set (a,b) or equivalently give a formula i→(a,b)?

2. Why do we have to do the diagonal enumeration? Why can’t you just write two nested loops which count a from 0 to infinity and b from 0 to infinity?

See later in the chapter for answers.

What Is Bigger Than Aleph-Zero?

Consider the real numbers, that is the rational numbers plus the irrationals. The reals are the set of infinite decimal fractions - you can use other definitions and get to the same conclusions. That is, a real number is something of the form:

integer. infinite sequence of digits

e.g.

12.34567891234567...

The reals include all of the types of numbers except of course the complex numbers. If the fractional part is 0 we have the integers. If the fractional part repeats we have a rational. If the factional part doesn’t repeat we have an irrational.

You also only have to consider the set of reals in the interval [0,1] to find a set that has more elements than the integers.

How to prove that this is true?

Cantor invented the diagonal argument for this and it has been used ever since to prove things like Gödel's incompleteness theorem, the halting problem and more. It has become a basic tool of logic and computer science.

To make things easy let's work in binary fractions. Suppose there is an enumeration that gives you all the binary fractions between 0 and 1. We don't actually care exactly what this enumeration is as long as we can use it to build up a table of numbers:

1    0.010101110111101...
 2    0.101110111010111...
 3    0.101101001011001...

and so on. All we are doing is writing down the enumeration i -> a binary real number for i an integer. 

If this enumeration exists then we have proved that there are as many reals as integers and vice versa and so the reals have an order of infinity that is aleph-zero i.e. they are countable.

If this is all true the enumerations contains all of the reals as long as you keep going. If we can find a real number that isn't in the list then we have proved that it isn't a complete enumeration and there are perhaps more reals than integers.

Now consider the following argument.

Take the first bit after the binary point of the first number and start a new number with its logical Boolean NOT - that is, if the bit is 0 use 1 and if it is 1 use 0. Next take the second bit from the second number and use its NOT for the second bit of the new number. In fact, you can see that the new number is simply the logical NOT of the diagonal of the table. In this case:

s=0.110...

This new number s is not equal to the first number in the table because it has been constructed to differ in the first bit. It is not equal to the second number because it has been constructed to be different in the second bit, and so on. In fact, you can see that s differs in the nth bit after the binary point from the nth number in the table.

We have no choice to conclude that s isn't in the table and so there is a real number that isn’t in the supposedly complete enumeration. In other words, there can be no such complete enumeration because if you present me with one I can use it to create a number that it doesn't include.

You cannot count the real numbers and there are more real numbers than there are integers.

Can you see why the argument fails if the fractions are not infinite sequences of bits?