Transfinite Set Theory
By Kevin Hartnett
Quanta Magazine, September 12, 2017
Edited by Andy Ross
Maryanthe Malliaris and Saharon Shelah have made a breakthrough that
disproves decades of conventional wisdom — two different variants of
infinity are actually the same size. Their work touches on the continuum
hypothesis and links with efforts to map mathematical complexity.
In
the 19th century, Georg Cantor proposed that two sets — finite or infinite —
have the same size, or cardinality, when they can be put into 1-1
correspondence with each other.
The set N of natural numbers is
infinite. The set of just the even numbers and the set of just the prime
numbers would seem to be smaller subsets of N. Yet Cantor defined a 1-1
correspondence for each of these infinite sets and N. He concluded that all
three sets are the same size, countable.
Cantor then proved that some
infinite sets are larger than the set N. The real numbers R form a
continuum. Cantor proved that R cannot be put into a 1-1 correspondence with
N: Even after you create an infinite list pairing natural numbers with real
numbers, you can always find another real number that never appears on your
list. So R is bigger than N. R is uncountable.
Cantor was unable to
decide whether there exists an intermediate cardinalities between those of N
and R. His conjecture that there is not is known as the continuum hypothesis
(CH). In 1940, Kurt Gödel proved that the CH is consistent with the axioms
of ZF set theory. In 1965, Paul Cohen proved that the CH is independent of
the axioms of ZF set theory.
Malliaris and Shelah proved that two
particular infinite sets p and t have equal cardinality:
— p is the
minimum size of a set of infinite subsets of N that have a strong finite
intersection property and no "pseudointersection" in the way the subsets
overlap.
— t is called the tower number and is the minimum size of a set
of subsets of N that is ordered by "reverse almost inclusion" with no
pseudointersection.
Both p and t are bigger than N and p is less than
or equal to t. If p were strictly less than t, then p would have a
cardinality between N and R. The CH would be false.
In 1967, H.
Jerome Keisler introduced an order to classify mathematical theories on the
basis of their complexity. He proposed a measure of complexity and proved
that theories fall into at least two classes: those that are minimally
complex and those that are maximally complex.
A decade or so later,
Shelah showed that there are natural jumps in complexity. Then, in her 2009
doctoral thesis, Malliaris did new work on Keisler’s order. In 2011, she and
Shelah started working together. In 2016, they published a 60-page paper in
the JAMS proving that p and t both have maximal complexity and the same
cardinality. In July 2017, they were awarded the Hausdorff medal in set
theory.
AR This is big, for me, who
worked on all this 40-odd years ago.
Ultimate L
By
Richard Elwes
New Scientist, July 30, 2011
Edited by Andy Ross
About 140 years ago, German mathematician Georg Cantor laid the foundations
of set theory. The set of whole numbers is "countable" infinity. The
infinity of points in a line is "continuum" infinity. Cantor showed not only
that the continuum is infinitely bigger than countable infinity, but also
that both are just steps in a staircase of higher infinities stretching up
into "absolute" infinity.
Cantor guessed there was no intermediate
level between countable infinity and the continuum. This is the continuum
hypothesis. But British mathematical philosopher Bertrand Russell showed in
1901 that although Cantor's conclusions about infinity were sound, the
logical basis of his set theory was flawed.
By 1922, German
mathematicians Ernst Zermelo and Abraham Fraenkel devised an axiomatisation
of set theory, now called ZF, that could support Cantor's tower of
infinities and stabilise the foundations of mathematics. But these axioms
delivered no clear answer on the continuum hypothesis.
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. Polish mathematicians
Stefan Banach and Alfred Tarski used the axiom to divide the set of points
defining a ball into six subsets which could then be slid around to produce
two balls of the same size as the original. This is the Banach-Tarski
paradox.
In 1931, Austrian logician Kurt Gödel published his
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 prove nor disprove.
Gödel had a hunch that
you can fill in most of these cracks in the structure of mathematics by
adding more levels of infinity on top of the staircase. In 1938, starting
from ZF sets and then carefully tailoring its infinite superstructure, Gödel
created a mathematical environment in which both the axiom of choice and the
continuum hypothesis are true. He called it the constructible universe, L.
L was an attractive environment in which to do mathematics, but 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 developed a method for producing a multitude of
mathematical universes to order, all of them compatible with ZF rules.
This was the beginning of a construction boom. Over the past
half-century, set theorists have discovered a vast jumble of possible models
of set theory. The existence of this mathematical multiverse seemed to dash
any hope of proving or disproving the continuum hypothesis.
As Cohen
showed, in some logically possible worlds the continuum 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
deciding which sort of world we occupy.
Hugh Woodin of the University
of California, Berkeley, has an answer. Woodin had earlier defined Woodin
cardinals, which are at a level far higher than Gödel's L. 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 these sets, so Woodin cardinals banish Banach-Tarski balls.
Woodin: "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? Set theory is riddled with unsolvability. Almost any question
you want to ask is unsolvable."
Woodin and others saw a new approach
while investigating patterns of real numbers in various L-type worlds. The
patterns, known as universally Baire sets, characterized the geometry
possible in a world and seemed to act as a kind of identifying code for it.
Woodin saw that relationships existed between the patterns in seemingly
disparate worlds. By patching the patterns together, he charted a single
mathematical superuniverse. He called it ultimate L.
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.
Cantor's continuum hypothesis turns out to be true.
Ultimate L
allows extra steps to be added to the top of the infinite staircase to fill
in gaps below. This is Gödel's idea for rooting out unsolvability in
mathematics. Gödelian incompleteness is chased up the staircase into the
infinite attic of mathematics.
At the XI International Workshop
on Set Theory, CIRM, Luminy, France, October 4-8, 2010,
Hugh Woodin gave
a three-part mini-course on ultimate L:
Part 1
Part 2
Part 3
Summary slide sets
Ultimate L
W.
Hugh Woodin, U. Penn.
PDF, 32
slides, 2010-10-15
The search for ultimate L
W.
Hugh Woodin, U. Michigan
PDF, 26 slides, 2010-11-02
The search for mathematical
truth
W. Hugh Woodin, Harvard U.
PDF, 47
slides, 2010-11-17
The Continuum Hypothesis
The Continuum Hypothesis, Part I
W. Hugh Woodin
Notices of the AMS, Vol 48, No 6, 2001
Cantor's Continuum
Hypothesis:
Suppose that X ⊆ R is an uncountable set.
Then there exists a bijection π : X → R.
The first
result concerning the Continuum Hypothesis, CH, was obtained by Gödel.
Theorem (Gödel). Assume ZFC is consistent. Then so is ZFC + CH.
The
modern era of set theory began with Cohen's discovery of the method of
forcing and his application of this new method to show:
Theorem (Cohen).
Assume ZFC is consistent. Then so is ZFC + "CH is false".
...
To summarize the current state of affairs for the theory of the projective
sets:
• Projective Determinacy is the correct axiom for the projective
sets; the ZFC axioms are obviously incomplete and, moreover, incomplete in a
fundamental way.
• Assuming Projective Determinacy, there are no
essential uses of the Axiom of Choice in the analysis of the standard
structure for Second Order Number Theory.
• The only known examples of
unsolvable problems about the projective sets, in the context of Projective
Determinacy, are analogous to the known examples of unsolvable problems in
number theory: Gödel sentences and consistency statements.
The Continuum Hypothesis, Part II
W. Hugh Woodin
Notices of the AMS, Vol 48, No 7, 2001
As we saw in Part I,
assuming the forcing axiom, Martin's Maximum, CH holds projectively in that
if X ⊆ R is an uncountable projective set, then |X| = |R|
.
...
So, is the Continuum Hypothesis solvable? Perhaps I am
not completely confident the "solution" I have sketched is the solution, but
it is for me convincing evidence that there is a solution. Thus, I now
believe the Continuum Hypothesis is solvable, which is a fundamental change
in my view of set theory.
AR Wonderful stuff — accords exactly with my intuitions about the cumulative hierarchy. If only I'd had the mathematical genius to do the hard work on the fine structure of L and the math of large cardinals. I struggled with both, back in the seventies.
 |
 |