Two infinities that are surprisingly equal

Gowers's Weblog 2018-03-10

It has been in the news recently — or rather, the small corner of the news that is of particular interest to mathematicians — that Maryanthe Malliaris and Saharon Shelah recently had an unexpected breakthrough when they stumbled on a proof that two infinities were equal that had been conjectured, and widely believed, to be distinct. Or rather, since both were strictly between the cardinality of the natural numbers and the cardinality of the reals, they were widely believed to be distinct in some models of set theory where the continuum hypothesis fails.

A couple of days ago, John Baez was sufficiently irritated by a Quanta article on this development that he wrote a post on Google Plus in which he did a much better job of explaining what was going on. As a result of reading that, and following and participating in the ensuing discussion, I have got interested in the problem. In particular, as a complete non-expert, I am struck that a problem that looks purely combinatorial (though infinitary) should, according to Quanta, have a solution that involves highly non-trivial arguments in proof theory and model theory. It makes me wonder, again as a complete non-expert so probably very naively, whether there is a simpler purely combinatorial argument that the set theorists missed because they believed too strongly that the two infinities were different.

I certainly haven’t found such an argument, but I thought it might be worth at least setting out the problem, in case it appeals to anyone, and giving a few preliminary thoughts about it. I’m not expecting much from this, but if there’s a small chance that it leads to a fruitful mathematical discussion, then it’s worth doing. As I said above, I am indebted to John Baez and to several commenters on his post for being able to write much of what I write in this post, as can easily be checked if you read that discussion as well.

A few definitions and a statement of the result

The problem concerns the structure you obtain when you take the power set of the natural numbers and quotient out by the relation “has a finite symmetric difference with”. That is, we regard two sets $A$ and $B$ as equivalent if you can turn $A$ into $B$ by removing finitely many elements and adding finitely many other elements.

It’s easy to check that this is an equivalence relation. We can also define a number of the usual set-theoretic operations. For example, writing $[A]$ for the equivalence class of $A$ , we can set $[A]\cap[B]$ to be $[A\cap B]$ , $[A]\cup [B]$ to be $[A\cup B]$ , $[A]^c$ to be $[A^c]$ , etc. It is easy to check that these operations are well-defined.

What about the subset relation? That too has an obvious definition. We don’t want to say that $[A]\subset[B]$ if $A\subset B$ , since that is not well-defined. However, we can define $A$ to be almost contained in $B$ if the set $A\setminus B$ is finite, and then say that $[A]\subset[B]$ if $A$ is almost contained in $B$ . This is well-defined and it’s also easy to check that it is true if and only if $[A]\cap[B]=[A]$ , which is the sort of thing we’d like to happen if our finite-fuzz set theory is to resemble normal set theory as closely as possible.

I will use a non-standard piece of terminology and refer to an equivalence class of sets as an f-set, the “f” standing for “finite” or “fuzzy” (though these fuzzy sets are not to be confused with the usual definition of fuzzy sets, which I don’t know and probably never will know). I’ll also say things like “is f-contained in” (which means the same as “is almost contained in” except that it refers to the f-sets rather than to representatives of their equivalence classes).

So far so good, but things start to get a bit less satisfactory when we consider infinite intersections and unions. How are we to define $\bigcap_{n=1}^\infty[A_n]$ , for example?

An obvious property we would like is that the intersection should be the largest f-set that is contained in all the $[A_n]$ . However, simple examples show that there doesn’t have to be a largest f-set contained in all the $[A_n]$ . Indeed, let $A_1\supset A_2\supset\dots$ be an infinite sequence of subsets of $\mathbb N$ such that $A_n\setminus A_{n+1}$ is infinite for every $n$ . Then $A$ is almost contained in every $A_n$ if and only if $A\setminus A_n$ is finite for every $n$ . Given any such set, we can find for each $n$ an element $b_n$ of $A_n\setminus A_{n+1}$ that is not contained in $A$ (since $A_n\setminus A_{n+1}$ is infinite but $A\setminus A_{n+1}$ is finite). Then the set $B=A\cup\{b_1,b_2,\dots\}$ is also almost contained in every $A_n$ , and $[A]$ is properly contained in $[B]$ (in the obvious sense).

OK, we don’t seem to have a satisfactory definition of infinite intersections, but we could at least hope for a satisfactory definition of “has an empty intersection”. And indeed, there is an obvious one. Given a collection of f-sets $[A_\gamma]$ , we say that its intersection is empty if the only f-set that is f-contained in every $[A_\gamma]$ is $[\emptyset]$ . (Note that $[\emptyset]$ is the equivalence class of the empty set, which consists of all finite subsets of $\mathbb N$ .) In terms of the sets rather than their equivalence classes, this is saying that there is no infinite set that is almost contained in every $A_\gamma$ .

An important concept that appears in many places in mathematics, but particularly in set theory, is the finite-intersection property. A collection $\mathcal A$ of subsets of a set $X$ is said to have this property if $A_1\cap\dots\cap A_n$ is non-empty whenever $A_1,\dots,A_n\in\mathcal A$ . This definition carries over to f-sets with no problem at all, since finite f-intersections were easy to define.

Let’s ask ourselves a little question here: can we find a collection of f-sets with the finite-intersection property but with an empty intersection? That is, no finite intersection is empty, but the intersection of all the f-sets is empty.

That should be pretty easy. For sets, there are very simple examples like $A_n=\{n,n+1,\dots\}$ — finitely many of those have a non-empty intersection, but there is no set that’s contained in all of them.

Unfortunately, all those sets are the same if we turn them into f-sets. But there is an obvious way of adjusting the example: we just take sets $A_1\supset A_2\supset\dots$ such that $A_n\setminus A_{n+1}$ is infinite for each $n$ and $\bigcap_{n=1}^\infty A_n=\emptyset$ . That ought to do the job once we turn each $A_n$ into its equivalence class $[A_n]$ .

Except that it doesn’t do the job. In fact, we’ve already observed that we can just pick a set $B=\{b_1,b_2,\dots\}$ with $b_n\in A_n\setminus A_{n+1}$ and then $[B]$ will be a non-empty f-intersection of the $A_n$ .

However, here’s an example that does work. We’ll take all f-sets $[A]$ such that $A$ has density 1. (This means that $n^{-1}|A\cap\{1,2,\dots,n\}|$ tends to 1 as $n$ tends to infinity.) Since the intersection of any two sets of density 1 has density 1 (a simple exercise), this collection of f-sets has the finite-intersection property. I claim that any f-set contained in all these f-sets must be $[\emptyset]$ .

Indeed, let $B$ be an infinite set and $(b_1,b_2,\dots)$ the enumeration of its elements in increasing order. We can pick a subsequence $(c_1,c_2,\dots)$ such that $c_n\geq 2^n$ for every $n$ , and the corresponding subset $C$ is an infinite subset of $B$ with density zero. Therefore, $\mathbb N\setminus C$ is a set of density 1 that does not almost contain $B$ .

The number of f-sets we took there in order to achieve an f-empty intersection was huge: the cardinality of the continuum. (That’s another easy exercise.) Did we really need that many? This innocent question leads straight to a definition that is needed in order to understand what Malliaris and Shelah did.

Definition. The cardinal p is the smallest cardinality of a collection $F$ of f-sets such that $F$ has the finite-intersection property but also $F$ has an empty f-intersection.

It is simple to prove that this cardinal is uncountable, but it is also known not to be as big as the cardinality of the continuum (where again this means that there are models of set theory — necessarily ones where CH fails — for which it is strictly smaller). So it is a rather nice intermediate cardinal, which partially explains its interest to set theorists.

The cardinal p is one of the two infinities that Malliaris and Shelah proved were the same. The other one is closely related. Define a tower to be a collection of f-sets that does not contain $[\emptyset]$ and is totally ordered by inclusion. Note that a tower $T$ trivially satisfies the finite-intersection property: if $[A_1],\dots,[A_n]$ belong to $T$ , then the smallest of the f-sets $[A_i]$ is the f-intersection and it isn’t f-empty. So let’s make another definition.

Definition. The cardinal t is the smallest cardinality of a tower $T$ that has an empty f-intersection.

Since a tower has the finite-intersection property, we are asking for something strictly stronger before, so strictly harder to obtain. It follows that t is at least as large as p.

And now we have the obvious question: is the inequality strict? As I have said, it was widely believed that it was, and a big surprise when Malliaris and Shelah proved that the two infinities were in fact equal.

What does this actually say? It says that if you can find a bunch $F$ of f-sets with the finite-intersection property and an empty f-intersection, then you can find a totally ordered example $T$ that has at most the cardinality of $F$ .

Why is the problem hard?

I don’t have a sophisticated answer to this that would explain why it is hard to experts in set theory. I just want to think about why it might be hard to prove the statement using a naive approach.

An immediate indication that things might be difficult is that it isn’t terribly easy to give any example of a tower with an empty f-intersection, let alone one with small cardinality.

An indication of the problem we face was already present when I gave a failed attempt to construct a system of sets with the finite-intersection property and empty intersection. I took a nested sequence $[A_1]\supset[A_2]\supset$ such that the sets $A_n$ had empty intersection, but that didn’t work because I could pick an element from each $A_n\setminus A_{n+1}$ and put those together to make a non-empty f-intersection. (I’m using “f-intersection” to mean any f-set f-contained in all the given f-sets. In general, we can’t choose a largest one, so it’s far from unique. The usual terminology would be to say that if $A$ is almost contained in every set from a collection of sets, then $A$ is a pseudointersection of that collection. But I’m trying to express as much as possible in terms of f-sets.)

Anyone who is familiar with ordinal hierarchies will see that there is an obvious thing we could do here. We could start as above, and then when we find the annoying f-intersection we simply add it to the tower and call it $[A_\omega]$ . And then inside $[A_\omega]$ we can find another nested decreasing sequence of sets and call those $[A_{\omega+1}], [A_{\omega+2}],\dots$ and so on. Those will also have a non-empty f-intersection, which we could call $[A_{2\omega}]$ , and so on.

Let’s use this idea to prove that there do exist towers with empty f-intersections. I shall build a collection of non-empty f-sets $[A_\alpha]$ by transfinite induction. If I have already built $[A_\alpha]$ , I let $[A_{\alpha+1}]$ be any non-empty f-set that is strictly f-contained in $[A_\alpha]$ . That tells me how to build my sets at successor ordinals. If $\alpha$ is a limit ordinal, then I’ll take $A_\alpha$ to be a non-empty f-intersection of all the $[A_\beta]$ with $\beta<\alpha$ .

But how am I so sure that such an f-intersection exists? I’m not, but if it doesn’t exist, then I’m very happy, as that means that the f-sets $[A_\beta]$ with $\beta<\alpha$ form a tower with empty f-intersection.

Since all the f-sets in this tower are distinct, the process has to terminate at some point, and that implies that a tower with empty f-intersection must exist.

For a lot of ordinal constructions like this, one can show that the process terminates at the first uncountable ordinal, $\omega_1$ . To set theorists, this has extremely small cardinality — by definition, the smallest one after the cardinality of the natural numbers. In some models of set theory, there will be a dizzying array of cardinals between this and the cardinality of the continuum.

In our case it is not too hard to prove that the process doesn’t terminate before we get to the first uncountable ordinal. Indeed, if $\alpha$ is a countable limit ordinal, then we can take an increasing sequence of ordinals $\alpha_n$ that tend to $\alpha$ , pick an element $b_n$ from $A_{\alpha_n}\setminus A_{\alpha_{n+1}}$ , and define $A_\alpha$ to be $\{b_1,b_2,\dots\}$ .

However, there doesn’t seem to be any obvious argument to say that the f-sets $[A_\alpha]$ with $\alpha<\omega_1$ have an empty f-intersection, even if we make some effort to keep our sets small (for example, by defining $A_{\alpha+1}$ to consist of every other element of $A_\alpha$ ). In fact, we sort of know that there won’t be such an argument, because if there were, then it would show that there was a tower whose cardinality was that of the first uncountable ordinal. That would prove that t had this cardinality, and since p is uncountable (that is easy to check) we would immediately know that p and t were equal.

So that’s already an indication that something subtle is going on that you need to be a proper set theorist to understand properly.

But do we need to understand these funny cardinalities to solve the problem? We don’t need to know what they are — just to prove that they are the same. Perhaps that can still be done in a naive way.

So here’s a very naive idea. Let’s take a set $F$ of f-sets with the finite intersection property and empty f-intersection, and let’s try to build a tower $T$ with empty intersection using only sets from $F$ . This would certainly be sufficient for showing that $T$ has cardinality at most that of $F$ , and if $F$ has minimal cardinality it would show that p=t.

There’s almost no chance that this will work, but let’s at least see where it goes wrong, or runs into a brick wall.

At first things go swimmingly. Let $[A]\in F$ . Then there must exist an f-set $[A']'\in F$ that does not f-contain $[A]$ , since otherwise $[A]$ itself would be a non-empty f-intersection for $F$ . But then $[A]\cap [A']$ is a proper f-subset of $[A]$ , and by the finite-intersection property it is not f-empty.

By iterating this argument, we can therefore obtain a nested sequence $[A_1]\supset[A_2]\supset$ of f-sets in $F$ .

The next thing we’d like to do is create $[A_\omega]$ . And this, unsurprisingly, is where the brick wall is. Consider, for example, the case where $F$ consists of all sets of density 1. What if we stupidly chose $A_n$ in such a way that $\min A_n\geq 2^n$ for every $n$ ? Then our diagonal procedure — picking an element from each set $A_n\setminus A_{n+1}$ — would yield a set of density zero. Of course, we could go for a different diagonal procedure. We would need to prove that for this particular $F$ and any nested sequence we can always find an f-intersection that belongs to $F$ . That’s equivalent to saying that for any sequence $A_1\supset A_2\supset$ of dense sets we can find a set $A$ such that $A\setminus A_n$ is finite for every $n$ and $A$ has density 1.

That’s a fairly simple (but not trivial) exercise I think, but when I tried to write a proof straight down I failed — it’s more like a pen-and-paper job until you get the construction right. But here’s the real question I’d like to know the answer to right at this moment. It splits into two questions actually.

Question 1. Let $F$ be a collection of f-sets with the finite-intersection property and no non-empty f-intersection. Let $[A_1]\supset[A_2]\supset\dots$ be a nested sequence of elements of $F$ . Must this sequence have an f-intersection that belongs to $F$ ?

Question 2. If, as seems likely, the answer to Question 1 is no, must it at least be the case that there exists a nested sequence in $F$ with an f-intersection that also belongs to $F$ ?

If the answer to Question 2 turned out to be yes, it would naturally lead to the following further question.

Question 3. If the answer to Question 2 is yes, then how far can we go with it? For example, must $F$ contain a nested transfinite sequence of uncountable length?

Unfortunately, even a positive answer to Question 3 would not be enough for us, for reasons I’ve already given. It might be the case that we can indeed build nice big towers in $F$ , but that the arguments stop working once we reach the first uncountable ordinal. Indeed, it might well be known that there are sets $F$ with the finite-intersection property and no non-empty f-intersection that do not contain towers that are bigger than this. If that’s the case, it would give at least one serious reason for the problem being hard. It would tell us that we can’t prove the equality by just finding a suitable tower inside $F$ : instead, we’d need to do something more indirect, constructing a tower $T$ and some non-obvious injection from $T$ to $F$ . (It would be non-obvious because it would not preserve the subset relation.)

Another way the problem might be difficult is if $F$ does contain a tower with no non-empty f-intersection, but we can’t extend an arbitrary tower in $F$ to a tower with this property. Perhaps if we started off building our tower the wrong way, it would lead us down a path that had a dead end long before the tower was big enough, even though good paths and good towers did exist.

But these are just pure speculations on my part. I’m sure the answers to many of my questions are known. If so, I’ll be interested to hear about it, and to understand better why Malliaris and Shelah had to use big tools and a much less obvious argument than the kind of thing I was trying to do above.