Goedel’s Incompeteness theorem surpassed?

Gödel’s Incompleteness Theorems are one of the cornerstone’s of modern mathematical thought but it is also a major blot on the mathematical landscape – as it establishes an inherent limit on the ability of mathematicians to describe the mathematical world: the first theorem (often thought of as the theorem) states that no consistent (ie self-contained) axiomatic system is capable to describing all the facts about natural numbers.

To today’s physical scientists – used to concepts such as relativity and quantum uncertainty – the broad idea that there could be an uncertainty at the heart of mathematics is maybe not so difficult to take, but it is fair to say it broke a lot of mathematical hearts in the 1930s when first promulgated. (This book – Godel’s Proof – offers an excellent introduction for the non-mathematician who is mathematically competent – ie like me!).

Gödel thought at the time that this kink in mathematical reality could be smoothed out by a better understanding of infinities in mathematics – and, according to the cover article in this week’s New Scientist (seemingly only available online to subscribers), by Richard Elwes, it is now being claimed by Hugh Woodin of UC Berkeley that just that has been shown.

Along the way, this new hypothesis of “Ultimate L” also demonstrates that Cantor’s continuum hypothesis is correct. I do not claim to understand “Ultimate L”, and in any case, as is their style, the New Scientist don’t print the proof, they just describe it in layman’s terms. I do have a basic understanding of the continuum hypothesis, though, and so can show the essential points that “Ultimate L” claims to have found.

Georg Cantor showed that there were multiple infinities, the first of which, so-called $\aleph_0$ (aleph null) is the infinity of the countable numbers – eg 1, 2, 3… and so on. Any infinite set that can be paired to a countable number in this way has a cardinality of $\aleph_0$. (And, as the New Scientist point out, this is the smallest infinity – eg if you thought that, say, there must be half as many even numbers as there are natural numbers, you are wrong – the set of both is of cardinality $\aleph_0$ – 2 is element 1 of the set, 4, is element 2 and so on: ie a natural number can be assigned to every member of the set of even numbers and so the set is of cardinality $\aleph_0$.)

The continuum hypothesis concerns what might be $\aleph_1$ – the next biggest infinity. Cantor’s hypothesis is that $\aleph_1$ is the real numbers (the continuum): I discuss why this is infinite and a different infinity from the natural numbers here.

We can show that this set has cardinality $2^{\aleph_0}$ – a number very much bigger than $\aleph_0$. But is there another infinity in between?

Mathematicians have concentrated on looking at whether any projections (a word familiar to me now from relational algebra) of the set of reals has a cardinality between $\aleph_0$ and $2^{\aleph_0}$ – if they did then it would be clear the reals could not have the cardinality of $\aleph_1$ – but some other, higher, $\aleph$.

No projections with a different cardinality have been found, but that is not the same as a proof they do not exist. But if Woodin’s theory is correct then none exist.

(Just one more chance to plug the brilliant Annotated Turing: if you are interested in computer science you should really read it! This is the book that first got me interested in all this.)

The diagonal proof

I am just reading Computability and Logic and it (or at least the old, 1980, edition I am reading) has a rather laboured explanation of Cantor’s 1891 proof of the non-enumerability of real numbers (the diagonal proof) so to reassure myself and because it is interesting I thought I’d set out a version here (closely modelled on that found in The Annotated Turing).

If you are already lost then – here’s what it’s about: it is a proof that the infinite number of real numbers (that is to say numbers with something after the decimal point eg 3.1) is a bigger infinity that the infinite number of integers – or if you want think in terms of fractions – the rational numbers. One – the infinite number of integers or rationals – is countable, the other is not.

This is a pretty mind-blowing proof and it is also fair to say that a minority of mathematicians have issues with Georg Cantor‘s theory of the continuum, but that is for another blog post, perhaps.

So here’s the example:

Let’s start setting out the real numbers that are less that one:

```0.00000000000..... 0.10000000000...... 0.20000000000...... 0.30000000000...... 0.40000000000...... 0.50000000000...... 0.60000000000...... 0.70000000000...... 0.80000000000..... 0.90000000000..... 0.01000000000..... 0.02000000000.... ..... 0.11000000000.....```

And so on. Now this looks like it might be enumerable (countable) by assigning an integer to element in the list- the first in the list is number 1, the second number 2 and so on. Hopefully you can see that this should, in theory, list all the numbers (except it doesn’t, as we will prove)

Bur let’s us take the number formed by the diagonal. In our case this is:

```0.00000000000..... 0.10000000000...... 0.20000000000...... 0.30000000000...... 0.40000000000...... 0.50000000000...... 0.60000000000...... 0.70000000000...... 0.80000000000..... 0.90000000000..... 0.01000000000..... 0.02000000000....```

ie `0.0000000000.......`

And let’s add 1 to every digit, so we get `0.111111111111....:` is this number in the list? We will now show you that it cannot be by checking off the numbers in the list one by one.

First of all, we can eliminate the first number in the list as a match, because its first digit is 0 and our number has 1 as the first digit. Then we can eliminate the second number in the list in the same way (ie it’s second digit does not match). In fact it is clearly the case that we can eliminate number N from the list because it will not match at digit N.

OK, you say, let’s fix that by adding this ‘new’ number to the list:

```0.11111111111...... 0.00000000000...... 0.10000000000...... 0.20000000000...... 0.30000000000...... 0.40000000000...... 0.50000000000...... 0.60000000000...... 0.70000000000...... 0.80000000000...... 0.90000000000...... 0.01000000000...... 0.02000000000......```

But let’s diagonalise that one:

```0.111111111111..... 0.00000000000...... 0.10000000000...... 0.20000000000...... 0.30000000000...... 0.40000000000...... 0.50000000000...... 0.60000000000...... 0.70000000000...... 0.80000000000...... 0.90000000000...... 0.01000000000...... 0.02000000000......```

And we get `0.1000000000......` Once again adding 1 to all the digits we get a new number `0.2111111111111....` – which we can show in the same way does not exist in the original list (set)

The importance of Turing’s findings

Yesterday I was speaking to a friend – who knows about computers but not about computer science – who told me this blog was just too difficult: so I thought I’d seek to order my own thoughts after reading The Annotated Turing and assist humanity in general (!) by writing a piece that explains what I think is the most fundamental finding from Turing’s famous On Computable Numbers paper.

To begin one must remember that Turing’s paper is not about electronic computers at all: indeed while in the paper he refers to “computers” – what he means is a person who computes.

Turing’s paper does describe an entirely theoretical mechanical machine that replicates the actions of a “computer” in solving a mathematical process through simple steps. You could think of those steps in this form if you were the computer adding 1 to 1:

• Read in the first number: 1
• Read in the operation: +
• Read in the second number: 1
• Apply the operation to both numbers

Turing’s argument is that the only numbers we can compute are those that can be computed in this mechanical way. This, in itself, was – and in a way remains – a controversial statement because it says that at the heart of human consciousness is a mechanical process and that, fundamentally, there is nothing special about consciousness.

In a way this flies in the face of all our experience of (digital) computers. Whatever else we know about them we know they cannot “think” – they are certainly mechanical (in the sense that they solve problems in the step-by-step way outlined above ) but they are so radically less powerful, it would seem, that our consciousness, our thinking must be built upon something else.

This – the idea that consciousness is more than mechanical – is rather out of favour these days but it still has its adherents: you can read more about the fascinating “hard problem of consciousness” if you want to read more about it, for here we are going to take the materialist approach and argue that the brain is indeed a mechanical processor, albeit one that (perhaps because of massive parallelism, or specific adaptation, or whatever) is hugely ahead of where our electronic computers are today in certain fields (though the gap is clearly closing on just about all fronts).

So if we accept that the only means available of calculating is a mechanical process then we must also accept Turing’s finding that we can only calculate a tiny minority of numbers or problems.

To explain this we need to look at the concept of infinity, or more properly infinities, because, at least according to the widely accepted theory of Georg Cantor, there is more than one infinity – indeed there are an infinite number of infinities all of a different size – or order as the size is referred too.

Sounds like nonsense, doesn’t it? But here’s a mind experiment to help you understand.

Think of a ruler, marked out in centimetres (or inches if you are old fashioned). But this ruler stretches on infinitely – so an infinite number of centimetre markings are present. But each one of these markings can be associated with a natural number, zero, one, two and so on. This is an infinite list which is said to be enumerable (countable) – a number can be assigned each member of the set of markings on the ruler. The number of members a set has is called its cardinality, and so this set has what is called the cardinality of aleph null:

But think of that ruler again – how many points are there between the different markings? Clearly we can divide the ruler up over and over again and that means we must have a bigger infinity than aleph zero.

This infinity is of this order  – two raised to the power of aleph null – we discuss why below:

An aside: the continuum hypothesis

According to the continuum hypothesis  aleph one is the so-called cardinality of the continuum. (Aleph one being the next biggest set of infinite numbers than aleph null: the continuum hypothesis):

And so, goes the theory, aleph one is of the same order as the number of real numbers. A real number being an integer number followed by a decimal point and an infinite (aleph null order) set of numbers – in the case of the natural numbers this is an infinite set of zeros, etc. Hence, the hypothesis states:

======

In any case the important number here is two to the power of aleph null – the order of the set of real numbers.

And why is this the order of the real numbers – because it is the order of the power set of the natural numbers. The power set is the number of subsets of a given set:

To explain why this is the order of the set of real numbers think of a binary (0 or 1) expansion after the decimal point – each digit will then be countable – ie there will be a first digit, a tenth digit and a ten millionth digit – that means it is of order aleph null, but the way in which the 0 and 1s can be ordered is the power set of the countable numbers, in other words two to the power of aleph null: a number that by definition is too big to count:

Now, what Turing’s paper shows is that we can only build a machine that computes (in other words calculate) a countable number of numbers – in other words we can only calculate aleph null numbers – or alternatively, solve aleph null problems.

But the number of real numbers is two to the power of aleph null, a much bigger number (to repeat, it is actually too big to count).

This is was a shattering result to a generate of mathematicians who were accustomed to the idea that all mathematical problems were solvable.

On 8 August 1900, one of greatest mathematicians of the nineteenth and twentieth century, David Hilbert, told the Second International Congress of Mathematicians in Paris:

“However unapproachable these [mathematical] problems may seem to us and however helpless we stand before them, we have, nevertheless, firm conviction that their solution must follow by a finite number of purely logical processes … This conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call. There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.”

But on 12 November 1936, the formal publication date of Turing’s paper, that confidence was destroyed for ever. An uncountable number of mathematical problems simply cannot be solved.