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.