Incompleteness in the natural world


Gödel Incompleteness Theorem
Gödel Incompleteness Theorem (Photo credit: janoma.cl)

A post inspired by Godel, Escher, Bach, Complexity: A Guided Tour, an article in this week’s New Scientist about the clash between general relativity and quantum mechanics and personal humiliation.

The everyday incompleteness: This is the personal humiliation bit. For the first time ever I went on a “Parkrun” today – the 5km Finsbury Park run, but I dropped out after 2.5km 2km – at the top of a hill and about 250 metres from my front door – I simply thought this is meant to be a leisure activity and I am not enjoying it one little bit. I can offer some excuses – it was really the first time ever I had run outdoors and so it was a bit silly to try a semi-competitive environment for that, I had not warmed up properly and so the first 500 metres were about simply getting breathing and limbs in co-ordination – mais qui s’excuse, s’accuse.

But the sense of incompleteness I want to write about here is not that everyday incompleteness, but a more fundamental one – our inability to fully describe the universe, or rather, a necessary fuzziness in our description.

Let’s begin with three great mathematical or scientific discoveries:

The diagonalisation method and the “incompleteness” of the real numbers: In 1891 Georg Cantor published one of the most beautiful, important and accessible arguments in number theory – through his diagonalisation argument, that proved that the infinity of the real numbers was qualitatively different from and greater than the infinity of the counting numbers.

The infinity of the counting numbers is just what it sounds like – start at one and keep going and you go on infinitely. This is the smallest infinity – called aleph null (\aleph_0 ).

Real numbers include the irrationals – those which cannot be expressed as fractions of counting numbers (Pythagoras shocked himself by discovering that \sqrt 2 was such a number). So the reals are all the numbers along a counting line – every single infinitesimal point along that line.

Few would disagree that there are, say, an infinite number of points between 0 and 1 on such a line. But Cantor showed that the number was uncountably infinite – i.e., we cannot just start counting from the first point and keep going. Here’s a brief proof…

Imagine we start to list all the points between 0 and 1 (in binary) – and we number each point, so…

1 is 0.00000000…..
2 is 0.100000000…..
3 is 0.010000000……
4 is 0.0010000000….
n is 0.{n – 2 0s}1{000……}

You can see this can go on for an infinitely countable number of times….

and so on. Now we decide to ‘flip’ the o or 1 at the index number, so we get:

1 is 0.1000000….
2 is 0.1100000….
3 is 0.0110000….
4 is 0.00110000….

And so on. But although we have already used up all the counting numbers we are now generating new numbers which we have not been able to count – this means we have more than \aleph_0 numbers in the reals, surely? But you argue, let’s just interleave these new numbers into our list like so….

1 is 0.0000000….
2 is 0.1000000…..
3 is 0.0100000….
4 is 0.1100000….
5 is 0.0010000….
6 is 0.0110000….

And so on. This is just another countably infinite set you argue. But, Cantor responds, do the ‘diagonalisation’ trick again and you get…

1 is 0.100000…..
2 is 0.110000….
3 is 0.0110000….
4 is 0.1101000…
5 is 0.00101000…
6 is 0.0110010….

And again we have new numbers, busting the countability of the set. And the point is this: no matter how many times you add the new numbers produced by diagonalisation into your counting list, diagonalisation will produce numbers you have not yet accounted for. From set theory you can show that while the counting numbers are of order (analogous to size) \aleph_0 , the reals are of order 2^{\aleph_0} , a far far bigger number – literally an uncountably bigger number.

Gödel’s Incompleteness Theorems: These are not amenable to a blog post length demonstration, but amount to this – we can state mathematical statements we know to be true but we cannot design a complete proof system that incorporates them – or we can state mathematical truths but we cannot build a self-contained system that proves they are true. The analogy with diagonalisation is that we know how to write out any real number between 0 and 1, but we cannot design a system (such as a computer program) that will write them all out – we have to keep ‘breaking’ the system by diagonalising it to find the missing numbers our rules will not generate for us. Gödel’s demonstration of this in 1931 was profoundly shocking to mathematicians as it appeared to many of them to completely undermine the very purpose of maths.

Turing’s Halting Problem: Very closely related to both Gödel’s incompleteness theorems and Cantor’s diagonalisation proof is Alan Turing’s formulation of the ‘halting problem’. Turing proposed a basic model of a computer – what we now refer to as a Turing machine – as an infinite paper tape and a reader (of the tape) and writer (to the tape). The tape’s contents can be interpreted as instructions to move, to write to the tape or to change the machine’s internal state (and that state can determine how the instructions are interpreted).

Now such a machine can easily be made of go into an infinite loop e.g.,:

  • The machine begins in the ‘start’ state and reads the tape.  If it reads a 0 or 1 it moves to the right and changes its state to ‘even’.
  • If the machine is in the state ‘even’ it reads the tape. If it reads a 0 or 1 it moves to the left and changes its state to ‘start’

You can see that if the tape is marked with two 0s or two 1s or any combination of 0 or 1 in the first two places the machine will loop for ever.

The halting problem is this – can we design a Turing machine that will tell us if a given machine and its instructions will fall into an infinite loop? Turing proved  we cannot without having to discuss any particular methodology … here’s my attempt to recreate his proof:

We can model any other Turing machine though a set of instructions on the tape, so if we have machine T we can have have it model machine M with instructions I : i.e., T(M, I)

Let us say T can tell whether M will halt or loop forever with instructions I – we don’t need to understand how it does it, just suppose that it does. So if (M, I) will halt T writes ‘yes’, otherwise it writes ‘no’.

Now let us design another machine T^\prime that takes T(M,I) its input but here T^\prime loops forever if T writes ‘yes’ and halts if T writes ‘no’.

Then we have:

M(I) halts or loops – T(M, I) halts – T^\prime loops forever.

But what if we feed T^\prime the input of T^\prime(T(M, I)?

M(I) halts or loops – T(M, I) halts – T^\prime(T(M,I)) loops forever – T^\prime(T^\prime(T(M,I))) – ??

Because if the second T^\prime(T^\prime(T(M,I))) halted then that would imply that the first had halted – but it is meant to loop forever, and so on…

As with Gödel we have reached a contradiction and so we cannot go further and must conclude that we cannot build a Turing machine (computer) that can solve the halting problem.

Quantum mechanics: The classic, Copenhagen, formulation of quantum mechanics states that the uncertainty of the theory collapses when we observe the world, but the “quantum worlds” theory suggests that actually the various outcomes do take place and we are just experiencing one of them at any given time. The experimental backup for the many worlds theory comes from quantum ‘double-slit’ experiments which suggest particles leave traces of their multiple states in every ‘world’.

What intrigues me: What if our limiting theories – the halting problem, Gödel’s incompleteness theorem, the uncountable infinite, were actually the equivalents of the Copenhagen formulation and, in fact, maths was also a “many world” domain where the incompleteness of the theories was actually the deeper reality – in other words the Turing machine can both loop forever and halt? This is probably, almost certainly, a very naïve analogy between the different theories but, lying in the bath and contemplating my humiliation via incompleteness this morning, it struck me as worth exploring at least.

Not a proof that aleph null and the order of the continuum are the same


Cantor's diagonal arguement
Cantor’s diagonal arguement (Photo credit: Wikipedia)

One final point from Wheels, Life and Other Mathematical Amusements– this time a “non-proof”.

Some argue that the order of the counting numbers, \aleph_0 is the same as that of the continuum – in other words that there is no difference in the scale of these two infinities.

Here is an argument that is sometimes advanced in this way, I found it initially seductive, but the proof it is wrong is actually very simple.

We simple assign an integer to every member of the continuum by “reversing” its order so, for instance:

1        0.1
2        0.2
3        0.3
4        0.4
5        0.5
6        0.6
7        0.7
8        0.8
9        0.9
10      0.01
11       0.11

100    0.001
101     0.101

And so on…

So what is the proof that this isn’t a proof that destroys Georg Cantor‘s work and rocks modern mathematics to its foundations? Well, in essence it is a restatement, in a slightly different way, of our old friend the diagonalisation argument.

No matter how long this list goes on for no number on the left hand side will ever have \aleph_0 digits. Hence no number on the right will ever represent an irrational. Hence it is impossible to assign a counting number to all the members of the set of the continuum.

Think of \frac{1}{3} – there could never be enough counting numbers to represent this as a decimal, as there will always be another 3 to add on at the end…

Don’t think about it too hard, though, as it bends the mind!

Another way of looking at the alephs


English: Georg Cantor
English: Georg Cantor (Photo credit: Wikipedia)

This is another insight gained from Wheels, Life and Other Mathematical Amusements– this time about the transfinite numbers.

The smallest transfinite number, so -called \aleph_0 is that of the countable infinity, or the counting numbers (the integers). Start at 1 (or 0) and keep going.

But how many sets can one make from the counting numbers? Well we know that for a set with n members there are 2^n possible subsets including the empty set \emptyset and the original set itself. Therefore we have 2^{\aleph_0} subsets of the integers.

So how big is 2^{\aleph_0}? The same size as the continuum, Georg Cantor‘s hypothesised \aleph_1 (i.e., the next biggest transfinite number) – though this hypothesis has never been proved and work continues on demonstrating there is a smaller transfinite number between \aleph_0 and the cardinality of the continuum.

Normally one sees the continuum explained as uncountable via the “diagonalisation argument” but the book makes a slightly different, if ultimately equivalent proof via contradiction:

Take all the subsets and assign an integer to each one.

If the integer is assigned to the subset containing the integer  which it has been assigned then label it ‘blue’, if the integer is assigned to a subset it does not contain then label it ‘red’.

So all the red integers themselves form a subset of the original set, can it be matched to a blue integer? No because then it would match to a subset that contained the integer, but as its red it cannot.

So can it then be matched with a red element? No because then a red element would be matched with a red element and should therefore be blue … a contradiction.

If you think about this for a bit you will also see it is directly equivalent to the diagonalisation argument and thus the cardinality of the subsets of the countable numbers is the same as that of the continuum.

The wheels of Aristotle


Sometimes you come across a thing where beauty matches simplicity, and Aristotle’s Wheel Paradox is just such a thing.

I came across it this afternoon after I returned to London from two too-short weeks away and a second-hand book I’d ordered, Wheels, Life and Other Mathematical Amusements, based on Martin Gardner‘s columns for the Scientific American.

I bought it because it has three chapters on Conway’s Game of Life – but the very first pages introduced me to Artistotle’s Wheel Paradox – which I’ll now explain…

Aristotle's Wheel Paradox

Imagine, as in the diagram above a small wheel that runs in parallel (eg., because it is attached) to a larger wheel. The large wheel runs on the line A to B, the smaller runs on C to D.

At every point the large wheel touches the line AB, an equivalent point on the small wheel touches CD: so there is a fixed and unique equivalent point on the small wheel for every point on the large wheel.

So that means when the large wheel has completed a revolution then so will the small wheel.

But if there is a fixed and unique equivalent point on the small wheel to every point on the large wheel that must surely imply their circumference is the same?

This is the paradox. And it’s one that puzzled many of the mathematical greats of past ages.

The solution is down to Georg Cantor and his formulation of the continuum. For there are an uncountable infinity of points on the rim of the two wheels. (Gardner describes this as Cantor’s Aleph-One\aleph_1 – and indeed Cantor thought it so – this is his continuum hypothesis – but it remains unproven that the continuum is indeed \aleph_1 as opposed to a higher \aleph .)

One final note – the book I bought is stamped “University Library Hull Withdrawn” and an online search suggests that this book is indeed no longer available to students at Hull. But how can it be justified that a major university gets rid of books in this way? Their loss, my gain though, of course.

“Ultimate L” explained


Hugh Woodin, American mathematician, at Berkeley
Image via Wikipedia

Well, that is what I wanted to write about – Hugh Woodin‘s theories of infinity, and indeed I found a blog that discussed a lot of this – http://caicedoteaching.wordpress.com/2010/10/19/luminy-hugh-woodin-ultimate-l-i/

But that is somewhat beyond me! And there does not appear to be a wikipedia article on this, so you may have to wait for some time before you see me try to take it on.

Interestingly, Woodin’s wikipedia entry, accurately, suggests that his earlier work was sceptical as to the truth of Cantor’s continuum hypothesis  – something that his latest work turns on its head.

Goedel’s Incompeteness theorem surpassed?


Portrait of Kurt Gödel, one of the most signif...
Image via Wikipedia

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


This is a pre-1909 image of Georg Cantor (he w...
Image via Wikipedia

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
  • Write out the answer

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:

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:

two to the power of aleph null

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):

aleph one

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:

aleph one equals two to the power of aleph null

======

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:

Powersets explainedTo 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:

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.