Posted by
Rich Murray-2 on
Aug 18, 2011; 3:11pm
URL: http://friam.383.s1.nabble.com/no-one-shall-expel-us-from-the-paradise-that-Cantor-has-created-Hugh-Woodin-s-ultimate-L-Richard-Elw8-tp6699752.html
"no one shall expel us from the paradise that Cantor has created",
Hugh Woodin's "ultimate L": Richard Elwes: Rich Murray 2011.08.18
http://www.newscientist.com/article/mg21128231.400-ultimate-logic-to-infinity-and-beyond.html?full=trueUltimate logic: To infinity and beyond
01 August 2011 by Richard Elwes
Magazine issue 2823.
The mysteries of infinity could lead us to a fantastic structure above
and beyond mathematics as we know it
WHEN David Hilbert left the podium at the Sorbonne in Paris, France,
on 8 August 1900, few of the assembled delegates seemed overly
impressed. According to one contemporary report, the discussion
following his address to the second International Congress of
Mathematicians was "rather desultory". Passions seem to have been more
inflamed by a subsequent debate on whether Esperanto should be adopted
as mathematics' working language.
Yet Hilbert's address set the mathematical agenda for the 20th
century. It crystallised into a list of 23 crucial unanswered
questions, including how to pack spheres to make best use of the
available space, and whether the Riemann hypothesis, which concerns
how the prime numbers are distributed, is true.
Today many of these problems have been resolved, sphere-packing among
them. Others, such as the Riemann hypothesis, have seen little or no
progress. But the first item on Hilbert's list stands out for the
sheer oddness of the answer supplied by generations of mathematicians
since: that mathematics is simply not equipped to provide an answer.
This curiously intractable riddle is known as the continuum
hypothesis, and it concerns that most enigmatic quantity, infinity.
Now, 140 years after the problem was formulated, a respected US
mathematician believes he has cracked it. What's more, he claims to
have arrived at the solution not by using mathematics as we know it,
but by building a new, radically stronger logical structure: a
structure he dubs "ultimate L".
The journey to this point began in the early 1870s, when the German
Georg Cantor was laying the foundations of set theory. Set theory
deals with the counting and manipulation of collections of objects,
and provides the crucial logical underpinnings of mathematics: because
numbers can be associated with the size of sets, the rules for
manipulating sets also determine the logic of arithmetic and
everything that builds on it.
These dry, slightly insipid logical considerations gained a new tang
when Cantor asked a critical question: how big can sets get? The
obvious answer - infinitely big - turned out to have a shocking twist:
infinity is not one entity, but comes in many levels.
How so? You can get a flavour of why by counting up the set of whole
numbers: 1, 2, 3, 4, 5... How far can you go? Why, infinitely far, of
course - there is no biggest whole number. This is one sort of
infinity, the smallest, "countable" level, where the action of
arithmetic takes place.
Now consider the question "how many points are there on a line?" A
line is perfectly straight and smooth, with no holes or gaps; it
contains infinitely many points. But this is not the countable
infinity of the whole numbers, where you bound upwards in a series of
defined, well-separated steps. This is a smooth, continuous infinity
that describes geometrical objects. It is characterised not by the
whole numbers, but by the real numbers: the whole numbers plus all the
numbers in between that have as many decimal places as you please -
0.1, 0.01, √2, π and so on.
Cantor showed that this "continuum" infinity is in fact infinitely
bigger than the countable, whole-number variety. What's more, it is
merely a step in a staircase leading to ever-higher levels of
infinities stretching up as far as, well, infinity.
While the precise structure of these higher infinities remained
nebulous, a more immediate question frustrated Cantor. Was there an
intermediate level between the countable infinity and the continuum?
He suspected not, but was unable to prove it. His hunch about the
non-existence of this mathematical mezzanine became known as the
continuum hypothesis.
Attempts to prove or disprove the continuum hypothesis depend on
analysing all possible infinite subsets of the real numbers. If every
one is either countable or has the same size as the full continuum,
then it is correct. Conversely, even one subset of intermediate size
would render it false.
A similar technique using subsets of the whole numbers shows that
there is no level of infinity below the countable. Tempting as it
might be to think that there are half as many even numbers as there
are whole numbers in total, the two collections can in fact be paired
off exactly. Indeed, every set of whole numbers is either finite or
countably infinite.
Applied to the real numbers, though, this approach bore little fruit,
for reasons that soon became clear. In 1885, the Swedish mathematician
Gösta Mittag-Leffler had blocked publication of one of Cantor's papers
on the basis that it was "about 100 years too soon". And as the
British mathematician and philosopher Bertrand Russell showed in 1901,
Cantor had indeed jumped the gun. Although his conclusions about
infinity were sound, the logical basis of his set theory was flawed,
resting on an informal and ultimately paradoxical conception of what
sets are.
It was not until 1922 that two German mathematicians, Ernst Zermelo
and Abraham Fraenkel, devised a series of rules for manipulating sets
that was seemingly robust enough to support Cantor's tower of
infinities and stabilise the foundations of mathematics.
Unfortunately, though, these rules delivered no clear answer to the
continuum hypothesis. In fact, they seemed strongly to suggest there
might even not be an answer.
Agony of choice
The immediate stumbling block was a rule known as the "axiom of
choice". It was not part of Zermelo and Fraenkel's original rules, but
was soon bolted on when it became clear that some essential
mathematics, such as the ability to compare different sizes of
infinity, would be impossible without it.
The axiom of choice states that if you have a collection of sets, you
can always form a new set by choosing one object from each of them.
That sounds anodyne, but it comes with a sting: you can dream up some
twisted initial sets that produce even stranger sets when you choose
one element from each. The Polish mathematicians Stefan Banach and
Alfred Tarski soon showed how the axiom could be used to divide the
set of points defining a spherical ball into six subsets which could
then be slid around to produce two balls of the same size as the
original. That was a symptom of a fundamental problem: the axiom
allowed peculiarly perverse sets of real numbers to exist whose
properties could never be determined. If so, this was a grim portent
for ever proving the continuum hypothesis.
This news came at a time when the concept of "unprovability" was just
coming into vogue. In 1931, the Austrian logician Kurt Gödel proved
his notorious "incompleteness theorem". It shows that even with the
most tightly knit basic rules, there will always be statements about
sets or numbers that mathematics can neither verify nor disprove.
At the same time, though, Gödel had a crazy-sounding hunch about how
you might fill in most of these cracks in mathematics' underlying
logical structure: you simply build more levels of infinity on top of
it. That goes against anything we might think of as a sound building
code, yet Gödel's guess turned out to be inspired. He proved his point
in 1938. By starting from a simple conception of sets compatible with
Zermelo and Fraenkel's rules and then carefully tailoring its infinite
superstructure, he created a mathematical environment in which both
the axiom of choice and the continuum hypothesis are simultaneously
true. He dubbed his new world the "constructible universe" - or simply
"L".
L was an attractive environment in which to do mathematics, but there
were soon reasons to doubt it was the "right" one. For a start, its
infinite staircase did not extend high enough to fill in all the gaps
known to exist in the underlying structure. In 1963 Paul Cohen of
Stanford University in California put things into context when he
developed a method for producing a multitude of mathematical universes
to order, all of them compatible with Zermelo and Fraenkel's rules.
This was the beginning of a construction boom. "Over the past
half-century, set theorists have discovered a vast diversity of models
of set theory, a chaotic jumble of set-theoretic possibilities," says
Joel Hamkins at the City University of New York. Some are "L-type
worlds" with superstructures like Gödel's L, differing only in the
range of extra levels of infinity they contain; others have wildly
varying architectural styles with completely different levels and
infinite staircases leading in all sorts of directions.
For most purposes, life within these structures is the same: most
everyday mathematics does not differ between them, and nor do the laws
of physics. But the existence of this mathematical "multiverse" also
seemed to dash any notion of ever getting to grips with the continuum
hypothesis. As Cohen was able to show, in some logically possible
worlds the hypothesis is true and there is no intermediate level of
infinity between the countable and the continuum; in others, there is
one; in still others, there are infinitely many. With mathematical
logic as we know it, there is simply no way of finding out which sort
of world we occupy.
That's where Hugh Woodin of the University of California, Berkeley,
has a suggestion. The answer, he says, can be found by stepping
outside our conventional mathematical world and moving on to a higher
plane.
Woodin is no "turn on, tune in" guru. A highly respected set theorist,
he has already achieved his subject's ultimate accolade: a level on
the infinite staircase named after him. This level, which lies far
higher than anything envisaged in Gödel's L, is inhabited by gigantic
entities known as Woodin cardinals.
Woodin cardinals illustrate how adding penthouse suites to the
structure of mathematics can solve problems on less rarefied levels
below. In 1988 the American mathematicians Donald Martin and John
Steel showed that if Woodin cardinals exist, then all "projective"
subsets of the real numbers have a measurable size. Almost all
ordinary geometrical objects can be described in terms of this
particular type of set, so this was just the buttress needed to keep
uncomfortable apparitions such as Banach and Tarski's ball out of
mainstream mathematics.
Such successes left Woodin unsatisfied, however. "What sense is there
in a conception of the universe of sets in which very large sets
exist, if you can't even figure out basic properties of small sets?"
he asks. Even 90 years after Zermelo and Fraenkel had supposedly fixed
the foundations of mathematics, cracks were rife. "Set theory is
riddled with unsolvability. Almost any question you want to ask is
unsolvable," says Woodin. And right at the heart of that lay the
continuum hypothesis.
Ultimate L
Woodin and others spotted the germ of a new, more radical approach
while investigating particular patterns of real numbers that pop up in
various L-type worlds. The patterns, known as universally Baire sets,
subtly changed the geometry possible in each of the worlds and seemed
to act as a kind of identifying code for it. And the more Woodin
looked, the more it became clear that relationships existed between
the patterns in seemingly disparate worlds. By patching the patterns
together, the boundaries that had seemed to exist between the worlds
began to dissolve, and a map of a single mathematical superuniverse
was slowly revealed. In tribute to Gödel's original invention, Woodin
dubbed this gigantic logical structure "ultimate L".
Among other things, ultimate L provides for the first time a
definitive account of the spectrum of subsets of the real numbers: for
every forking point between worlds that Cohen's methods open up, only
one possible route is compatible with Woodin's map. In particular it
implies Cantor's hypothesis to be true, ruling out anything between
countable infinity and the continuum. That would mark not only the end
of a 140-year-old conundrum, but a personal turnaround for Woodin: 10
years ago, he was arguing that the continuum hypothesis should be
considered false.
Ultimate L does not rest there. Its wide, airy space allows extra
steps to be bolted to the top of the infinite staircase as necessary
to fill in gaps below, making good on Gödel's hunch about rooting out
the unsolvability that riddles mathematics. Gödel's incompleteness
theorem would not be dead, but you could chase it as far as you
pleased up the staircase into the infinite attic of mathematics.
The prospect of finally removing the logical incompleteness that has
bedevilled even basic areas such as number theory is enough to get
many mathematicians salivating. There is just one question. Is
ultimate L ultimately true?
Andrés Caicedo, a logician at Boise State University in Idaho, is
cautiously optimistic. "It would be reasonable to say that this is the
'correct' way of going about completing the rules of set theory," he
says. "But there are still several technical issues to be clarified
before saying confidently that it will succeed."
Others are less convinced. Hamkins, who is a former student of
Woodin's, holds to the idea that there simply are as many legitimate
logical constructions for mathematics as we have found so far. He
thinks mathematicians should learn to embrace the diversity of the
mathematical multiverse, with spaces where the continuum hypothesis is
true and others where it is false. The choice of which space to work
in would then be a matter of personal taste and convenience. "The
answer consists of our detailed understanding of how the continuum
hypothesis both holds and fails throughout the multiverse," he says.
Woodin's ideas need not put paid to this choice entirely, though:
aspects of many of these diverse universes will survive inside
ultimate L. "One goal is to show that any universe attainable by means
we can currently foresee can be obtained from the theory," says
Caicedo. "If so, then ultimate L is all we need."
In 2010, Woodin presented his ideas to the same forum that Hilbert had
addressed over a century earlier, the International Congress of
Mathematicians, this time in Hyderabad, India. Hilbert famously once
defended set theory by proclaiming that "no one shall expel us from
the paradise that Cantor has created". But we have been stumbling
around that paradise with no clear idea of where we are. Perhaps now a
guide is within our grasp - one that will take us through this century
and beyond.
Richard Elwes is a teaching fellow at the University of Leeds in the
UK and the author of Maths 1001: Absolutely Everything That Matters in
Mathematics (Quercus, 2010) and How to Build a Brain (Quercus, 2011)
within mutual service, Rich Murray
[hidden email] 505-819-7388 Skype audio, video rich.murray11
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at
http://www.friam.org