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


One response to “Goedel’s Incompeteness theorem surpassed?”

  1. […] cartesian product Stuff about computing Skip to content HomeAbout ← Goedel’s Incompeteness theorem surpassed? […]

%d bloggers like this: