|Programmer's Guide To Theory - In Search Of Aleph-One|
|Written by Mike James|
|Monday, 25 January 2021|
Page 1 of 3
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.
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:
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.
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
The reals include all of the types of numbers except of course the complex numbers. If the fractional part is
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:
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
This new number
We have no choice to conclude that
Can you see why the argument fails if the fractions are not infinite sequences of bits?
|Last Updated ( Monday, 25 January 2021 )|