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.

In fact it is easier and more general to consider the set (a,b) where a and b are natural numbers. 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.

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 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 zero is also just boring standard infinite.

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.

Can you write a for loop that enumerates the point set (a,b) or equivalently give a formula i->(a,b)?

Why do we have to do the diagonal enumeration? Why cant you just write two nested loops which count a from 0 to infinity and b from 0 to infinity?

So 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. 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 prover things like Godel's incompleteness theorem 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 0 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 in the table.

We have no choice to conclude that s isn't in the table and so there is a real number not 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?

Aleph One and beyond

The size of the real numbers is called Aleph One and it is the size of the continuum.

Aleph Zero is also the sort of infinity we usually denote by ∞ and so Aleph One is bigger than our standard sort of countable infinity.

This all seems a little shocking - we now have two infinities.

You can show that Aleph One behaves in the same way as Aleph Zero in the sense that you can take any lots of elements away, even Aleph One elements, and there are still Aleph One elements left and so on.

If you look at the way that the proof works you can see that the reason why you can't count the real numbers is that there is a sort of double infinity involved. To count them you would need one infinite for loop to generate a particular real number i.e. an infinite sequence of digits  and one infinite for loop to generate each of the reals. Something like:

for each real number
 for each digit of the real number


and both loops are assumed countably infinite.

Of course, the problem with these loops is that the inner loop never ends so the outer one never gets to step on to the next real number in the enumeration.

This raises the question of what we did to get from Aleph Zero to Aleph One - and can we repeat it to get to Aleph Two?

The answer is yes.

If two sets A and B are Aleph Zero in size then we already know that all of the usual set operations A U B and A X B for example also have Aleph Zero elements. However, there is another operation that we haven't considered - the power set.

If you have a set of elements A, then the power set of A, usually written 2^A, is the set of all subsets of A including the empty set and A.

So if A={a,b} the power set is {0,{a},{b}, A}.

You can see why it is called the power set as a set with two things in it gives rise to a power set with four things, i.e. 2²=4.

This is generally true and if A has n elements its power set has 2ⁿ elements.

Notice that this is a much bigger increase than other set operations:
A U A has 2n elements and AXA has n² elements

The power set really does seem to change gear on the increase in the number of elements. So much so that if A has Aleph Zero elements then it can be proved that 2^A, i.e. the power set, has Aleph One elements. And yes, if A has Aleph One elements it's power set has Aleph Two elements and so on.

In general if A has Aleph n elements, the power set 2^A has Aleph n+1 elements.

There is an infinity of orders of infinity.

Notice also that the reals are related to the power set of the integers, just as the rational are related to the Cartesian product of the integers, i.e. R=2^Z and Q=ZXZ with suitable definitions and technical adjustments.

The set of Alephs is called the transfinite numbers and it is said that this is what sent Cantor crazy.

So finally - and someone would ask - are there Aleph Zero transfinite numbers or more?

The answer is we don't know and it all hinges on the answer to the question "is there a set with an order of infinity between Aleph Zero and Aleph One".

That there isn't is the so-called Continuum hypothesis, and it forms Hibert's 23rd problem and here we get into some very deep mathematics and an area of active research.

A Programmers Guide To Theory
First Draft

There is a more recent version of this:

Now available as a paperback and ebook from Amazon.

A Programmers Guide To Theory - NP & Co-NP

Contents

1. What Is Computable?
2. Finite State Machines
3. What is a Turing Machine? 
4. Computational Complexity
5. Non-computable numbers
6. The Transfinite
7. Axiom Of Choice
8. Lambda Calculus
9. Grammar and Torture
10. Reverse Polish Notation - RPN
11. Introduction to Boolean Logic
12. Confronting The Unprovable - Gödel And All That
13. The Programmer's Guide to Fractals
14. The Programmer's Guide to Chaos*
15. Prime Numbers And Primality Testing
16. Cellular Automata - The How and Why
17. Information Theory
18. Coding Theory
19. Kolmogorov Complexity

*To be revised

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:0486469212>

<ASIN:0814758371>

<ASIN:0393339289>