A Word on Cardinality – Diagonal Arguments

Cantor’s Diagonal Argument – Different Sizes of Infinity

In 1874 Georg Cantor – the father of set theory – made a profound discovery regarding the nature of infinity. Namely that some infinities are bigger than others. This can be seen as being as revolutionary an idea as imaginary numbers, and was widely and vehemently disputed by Cantor’s contemporaries such as Henri Poincaré who called his ideas a “grave disease”. That said, his work is now so well established as to be considered foundational information in any serious study of mathematics. The story begins with the notion of a countable set, we think of the natural numbers as being countable in that we can put them in a list and count through them (clearly we will never reach the end of the list, but the process of counting them makes sense). This is somehow the building block for defining countable sets, as we think of a general set as being countable if there exists a bijection between it and . Wikipedia does a good job at explaining the notion of bijection if you don’t know it.

Example: The rational numbers are countable

The rationals . We can show they are countable by writing them in a table as follows

First notice that every rational number occurs in this table, and that, by snaking along the pink path we will hit every number in it. In this way we have a list with every rational number in it, and thus the rationals are countably infinite. Our list beginning 1/1, 2/1, 1/2, 1/3, etc.

So a question is: are the real numbers countable? Another question is are all infinite sets countable? Cantor answered both in the negative with the following very simple, yet powerful argument. Suppose that the real interval were a countable set. That is, we could write down every real number between 0 and 1 in some list. Let me write a small section of this hypothetical list below:

Now here the numbers stretch off infinitely into the right, as real numbers can have infinite decimal expansions, and obviously stretch infinitely far down. The letters represent numbers between 0 and 9, so may be the number 0.12321… . It is unimportant what the specific numbers are, only that we can write them in such a list. Now, along the diagonal of this list the numbers that have been emboldened form a number; it begins . With this we define a new number, called D, by adding 1 to each digit with the convention that if a digit is 9 then adding 1 goes to 0. In this way we have that the first digit of D is . So if the first number really did start 0.12321, then D would start 0.2…, for example. Now this number D is surely a real number, and moreover it certainly lies between 0 and 1. Thus if the above list is, as claimed, complete it should contain D. But here is where we reach an impass – for the first digit of D is different from the first digit of the first number (indeed ), the second digit of D is different from the second digit of the second number (), and so on. In this way we see that D is different from every number on the list, and so can’t be on the list at all. This show that the real unit interval [0,1] is not countably infinite. And since this sits within the real number line, we can also deduce that the real numbers are uncountably infinite. Cantor’s diagonal argument, as this proof is known not only gave rise to a new concept of different sizes, or cardinalities, of infinity, but also gave a powerful new technique for proof that has since popped up in various places in mathematics (and elsewhere…).

Primitive Recursive Functions

What is a primitive recursive function? When Gödel went about proving his incompleteness theorem he developed an axiomatic system called Typographical Number Theory, or TNT. He was mainly thinking about Principia Mathematica at the time, but developed TNT in such a way that it was easier to  make a proof, yet his theorem still applied to Principia Mathematica. These formal systems consist of a fixed amount of symbols, some rules for manipulating them, and some axioms (which are just strings of these symbols to which the manipulation rules can be applied to derive new strings of symbols). The power of such systems come from the association of ‘meaningful’ statements with stings of symbols, so to would tell us something about numbers, namely that there exists a number such that 1 plus that number equals 2. Using very few axioms one is able to make huge amounts of ‘meaningful’ statements about number theory, for example on primality of a number or Fermat’s last theorem.

We could play a similar game with a computer programme. Fix a given set of symbols which from which code can be formulated, say

A,B,C,…,Z, “, [, ], :, ;, <, >, +, x, =, <=

and the programme then implements its own interpretation (or at least its writers’ interpretation!). We require a few in-built functions that our programme can compute, say adding two natural numbers, multiplying two natural numbers, determining if two numbers are equal or if one is greater or less then another. With this we can define new functions in the programme, for instance a programme for division may be something like

DEFINE “DIVIDE”[M,N]:

BLOCK 0: BEGIN

            IF M<N THEN:

            QUIT BLOCK 0;

            LOOP AT MOST M+1 TIMES

            BLOCK 1: BEGIN

                        IF OUTPUT x N=M THEN:

                        ABORT LOOP 1;

                        OUTPUT <= OUTPUT + 1;

                        BLOCK 1: END;

            BLOCK 0: END

A key point is that the loops should terminate in a finite time, in this example in at most M+1 steps. Then we have defined a new function, called DIVIDE, which takes two inputs M, N and outputs M/N if M divides N, else outputs 0 (if M<N) or M+1 (if M/N has non-zero remainder). We could use this to write, again a huge number of functions, to test for many different properties of the natural numbers e.g to test if a number is prime, or if it satisfies Goldbach’s conjecture. Functions that can be written in this programme are given the name primitive recursive functions. Let’s give a name to this programme, call it PR-programme. Believably, if a function is PR-programmable then it is represented in TNT. As mentioned above there are a huge number of functions that PR can carry out: is a number prime, perfect, a square, a cube, a factorial, a Fibonacci number. It is not an unreasonable to ask: is every function a primitive recursive function? A more grass-roots way of asking this question is

Does there exist a test that will terminate in a predictably finite time for every property of the natural numbers?

This is not asking that we have a complete understanding of every property of the natural numbers, just that we can, say, check them for a given number. For example – we do not have a complete understanding of the primes, but if you give me a number, say 143233, I can write a PR-programme that tests if this is prime, simply by checking every possible product of numbers less then it. This will terminate in a predictably finite number of steps. The question does not also demand that we know the programme that will carry out such a test, just that one exists hypothetically. It may be the case that we just haven’t worked out the correct PR-programme to test for certain functions yet, and that doesn’t give a negative answer, we need to show that there exists properties such that no such programme can ever exist. So for this question to be answered in the negative would be to say that there are some really messed up properties of the natural numbers.

A Diagonal Proof That Not All Functions Are Primitive Recursive

We can indeed prove that not all functions are primitive recursive, and in a similar way to Cantor’s diagonal method. Restrict our attention to functions in one variable. Start by making the assumption that every function is primitive recursive. If every function were PR-programmable then we could list them according to the following ordering: order the programmes by length, and if any two programmes have the same length order them by an ‘alphabetical style’ ordering. Note: it is only ‘alphabetical’-style because there are more symbols used then just the alphabet, so we need to decide if < is before or after ], and so on. But once we fix an ordering everything follows trivially. So lets write the beginning of this list down, starting with the shortest programme:

PR-programme#1[N]

PR-programme#2[N]

PR-programme#3[N]

PR-programme#4[N]

So here PR-programme#k[N] takes the input N an outputs some natural number. Okay, now I will define a new function called Diagonal[N] as follows:

Diagonal[N]=PR-programme#N[N]+1

Diagonal[N] takes the Nth programme on our list, inputs N, and then adds 1. Now if this function were primitive recursive then it would exist on the list somewhere. Lets say it is the Mth function on the list. However, if we input M into the function Diagonal something contradictory happens: we get, by the definition of Diagonal,

Diagonal[M]=PR-programme#M[M]+1

but also, since Diagonal is the Mth function on the list, that

Diagonal[M]=PR-programme#M[M]

And hence, since PR-programme#M[M]+1  is different from PR-programme#M[M], we see that Diagonal is not the Mth programme on the list. But M was, of course, arbitrary, and so Diagonal is not on the list at all. We have thus shown that not all functions are primitive recursive.

Directions

Douglas Hofstadter gives a more complete account of PR-programmes, primitive recursive functions and of the above arguments in his brilliant book “Gödel, Escher, Bach”, in Chapter 13, and  goes on to complete the proof of Gödel’s Incompleteness Theorem in the next chapter. There are many profound , perplexing and pervasive consequences to both mathematics and philosophy as a result of these works, many of which are covered in Hofstadter’s book. For example: what would we change, if anything, by allowing infinite loops in our PR-programme? And if the reals are bigger then the rationals, are they the biggest infinity, or are there others? These are merely drops in a pond that it is well worth wholeheartedly dunking your head into.

Advertisement