Programmer's Guide To Theory - In Search Of Aleph-One
Written by Mike James   
Monday, 25 January 2021
Article Index
Programmer's Guide To Theory - In Search Of Aleph-One
Finite But Unbounded
Aleph-One And Beyond

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.

cover600

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 ***NEW!
  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
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. Algorithm of Choice
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus
    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. 

diagonal

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.

aleph0aleph1

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



Last Updated ( Monday, 25 January 2021 )