Large Sets 11
Posted by Tom Leinster
Previously: Part 10. Next: Part 12
Measurability is the largest of the “large set” conditions I’m going to talk about in this series. Today I’ll explain how measurability relates to inaccessibility, say a tiny bit about how measurability can arise in analysis problems, and say somewhat more about measurability and codensity monads.
Let’s recall the definition: an uncountable set is measurable if it admits a nonprincipal ultrafilter that is -complete — in other words, closed under -fold intersections for all .
We’ll see that if there are any measurable sets at all, they must be enormous. In particular, measurable sets are inaccessible, but there are many many inaccessible sets smaller than the smallest measurable set. In Part 9.5, Mike talked about the various levels of size between inaccessible and measurable: 1-inaccessible, 2-inaccessible, hyperinaccessible, Mahlo, greatly Mahlo, … I recommend it! But here I’m going to stick to measurable versus inaccessible.
Let’s start by showing that every measurable set is inaccessible. (And at the same time, I’ll remind you what inaccessible means.) Let be a measurable set. To show that is inaccessible, we have to prove three things:
is uncountable. This is an explicit part of the definition of measurability.
is regular. In other words, it’s impossible to express as a union with and for all .
The key here is an observation about nonprincipal -complete ultrafilters. Each member of such an ultrafilter must have cardinality : for if not, would be a union of singletons, and since singletons aren’t in the ultrafilter, neither is .
Since is measurable, there is some nonprincipal -complete ultrafilter on it. If is a family of subsets of with and , then it follows from our observation that no belongs to . Since , the union is not in either, so it definitely can’t be .
is a strong limit. In other words, if then .
This can be proved using a nice lemma: for sets and , any ultrafilter on closed under both - and -fold intersections must be principal. I leave the proof to you, but it’s quite satisfying — try it! Rot-13ed hint: Sbe rnpu n va N, pbafvqre gur shapgvba sebz O^N gb O tvira ol rinyhngvat ng n.
Against my usual preference, I’ll use contradiction to prove that any measurable set is a strong limit. Let and be sets, suppose that , and let be an -complete ultrafilter on . We’ll show that is principal.
For take an injection . Pushing forward along gives an -complete ultrafilter on . Then is closed under -fold intersection, so by the lemma, is principal. Since is injective, is principal, as required.
We’ve just shown that every measurable set is inaccessible, a result first proved by Stanisław Ulam in 1930. For what happened next historically, I’ll quote from Akihiro Kanamori’s book The Higher Infinite (p.27):
Whether the least measurable cardinal is strictly larger than the least inaccessible cardinal became a focal question, and was settled only thirty years later. For a result that by present-day standards is rather straightforward this may seem like a remarkably long time — even taking into account the convulsive events that took place in Europe. However, this is a typical case of a long-standing mathematical problem suddenly solved in the wake of new techniques.
Kanamori doesn’t say it here, but the answer to the question is yes. So the theorem is:
For every measurable set , there exists an inaccessible set .
In fact, something much stronger is true:
For every measurable set , there are isomorphism classes of inaccessible sets .
There certainly aren’t more than of them, for reasons that have nothing to do with largeness axioms: for any set whatsoever, there are at most iso classes of sets . So the force of the theorem is that there are as many as inaccessible sets smaller than any measurable set .
This stronger result has a corollary:
For every measurable set , there are unboundedly many inaccessibles .
That is, for any , there is some inaccessible set with . For if not, would be an upper bound for the inaccessibles , so there would be at most inaccessibles , contradicting the previous theorem.
And this corollary in turn has a corollary:
It is consistent with ETCS + (there are unboundedly many inaccessibles) that there are no measurable sets.
The argument is the same one that’s appeared in many of these posts. Take a model of ETCS with unboundedly many inaccessibles. Call a set in it “small” if it’s every measurable set. Then by the previous corollary, the small sets are a model of ETCS in which there are unboundedly many inaccessible sets but no measurable sets.
The theorem that beneath every measurable set there are inaccessibles is by far the hardest result that I’ve mentioned in these posts — as you might guess from that thirty-year gap. The proof is, I think, quite interesting, so I’m going to describe it.
If you’re skim-reading this post, or if you want to get on to the part where I talk about connections with category theory, then you might want to skip ahead to the end of the long bulleted list below.
I’m going to sketch the proof of the theorem, but first I want to highlight a particular feature: it’s one of those mathematical arguments where a thing is proved to exist by showing that the set of such things has positive measure. Such proofs are maybe most familiar from analysis, but the same strategy is behind the probabilistic method in combinatorics.
In the case at hand, “measure” refers to an ultrafilter. We have our measurable set , we have the set
and the proof will construct an ultrafilter on with the property that the set of inaccessible sets belongs to the ultrafilter. This immediately implies that there’s at least one inaccessible set , as does not belong to any ultrafilter. In fact, the ultrafilter has properties implying that every member of it has cardinality , and this gives the full-strength result: there are iso classes of inaccessible sets .
So we won’t actually construct inaccessible sets . We’ll just show that there are that many of them.
I’ll now sketch a proof that when is measurable, there are isomorphism classes of inaccessible sets . It’s the argument you’ll find in some set theory texts, rewritten in a structural/neutral style. Here we go.
Choose a nonprincipal -complete ultrafilter on , which we can because is measurable.
Define to be the set quotiented by the equivalence relation that identifies two functions when their equalizer belongs to . (If you know about ultraproducts then you’ll recognize that this is one.) Write for the equivalence class of a function .
Define a relation on by and check that this is well-defined.
Show that is a well-order on . Ultimately this is because cardinal inequality is a well-order on , but the tricky part of this step is the “well”.
The usual definition of well-order says that every nonempty subset has a least element. But in this step, it’s better (essential?) to use the equivalent condition that there are no countably infinite descending chains . The uncountability of is also needed in this step.
Each gives rise to an element of , namely, the equivalence class of the constant function with value . Call such elements of constant.
Show that in , the set of constant elements is downwards closed, but not every element is constant. One way to construct a nonconstant element is to choose an arbitrary well-order on and take the equivalence class of the function .
Since is well-ordered and not every element is constant, it has a least nonconstant element . Then everything smaller than is constant.
Push the ultrafilter on forward along to give an ultrafilter on . Since is -complete, so is . Since is not constant, is not principal.
Show that:
- the set of iso classes of uncountable sets belongs to ;
- the set of iso classes of strong limits belongs to ;
- the set of iso classes of regular sets belongs to .
I’m not going to go into the details of these substeps. For the most part, they’re the kind of arguments that you’ll be used to if you’re used to ultraproducts, although there are some not-quite-routine aspects too. In any case, putting together these three results immediately gives:
- the set of iso classes of inaccessible sets belongs to .
Since is a nonprincipal -complete ultrafilter, every member has cardinality . But it’s an ultrafilter on , which is , so every member has the same cardinality as . In particular, the set of iso classes of inaccessible sets has cardinality .
That’s it! As I said, it’s much more substantial than any other proof in this series. If you know of a simpler proof, please let me know in the comments.
I promised to say a tiny bit about the connections with analysis. Of course, the concept of measurable set came from analysis historically, but the existence of a measurable set can also be relevant to analysis problems that arise naturally to this day.
Here’s a specific example, from the 1987 book An Introduction to Independence for Analysts by the analyst Garth Dales and the set theorist Hugh Woodin. Recall that the class of Borel sets in a topological space is the -algebra generated by the open sets. That is, it’s the smallest class of subsets containing the open sets and closed under complements and countable unions. Dales and Woodin write (p.viii):
It is not difficult to show that, if is a continuous function, then is Lebesgue measurable for each Borel subset of . Now suppose that are continuous functions. Is Lebesgue measurable for each Borel set ? This problem cannot be decided in ZFC. However if there is a measurable cardinal, then these sets are indeed all Lebesgue measurable.
So the measurability of certain subsets of can be affected by the existence of a measurable set — which is necessarily much, much, bigger than .
I’ll finish by talking about how measurability of sets arises in category theory.
Throughout this post and the previous one, I’ve used the correspondence between collections of subsets of (such as ultrafilters) and functions (such as measures). But what I haven’t mentioned is the correspondence between measures and integral operators. Given how basic that is to analysis, it’s probably worth thinking about in this context too.
Take a set and a -valued probability measure on , defined on every subset of . What kind of function on can we integrate against ? That is, when does the expression
define an element of in some reasonable way?
Well, if is constant on some subset of of measure then the integral certainly makes sense: it should be the constant value of . (Remember that is a probability measure: .) Since is countably additive, this is guaranteed to happen when is countable. So, determines an “integration” operator
for each countable set .
Exactly as in analysis, measures and integration operators are in one-to-one correspondence, as long as you set things up right. In this case, we define an integration operator on to be a family of maps
natural in countable sets . Then the following three kinds of structure on are essentially the same, in the sense of being in bijection with one another:
integration operators on ;
-valued probability measures on ;
ultrafilters on closed under countable intersection.
And now we get to something categorically significant. Write for the set of integration operators on . Then is a functor . In fact, it’s more than just a functor: it’s a monad, the codensity monad of the inclusion
of the category of countable sets into the category of sets.
If you like ends, you’ll find it enlightening to write as one:
This is an instance of the general end formula for a codensity monad. Alternatively, the fact that is this codensity monad follows from the original definition of as a set of natural transformations.
In summary, the codensity monad of assigns to each set the set of ultrafilters on closed under countable intersections. Some elements of are trivial: there’s the principal ultrafilter for each . And predictably, the unit of the monad is the assignment .
But the question is, are there ever any other elements of ?
Thinking set-theoretically, the answer is yes if and only if there is some countably measurable set. As we saw last time, is equivalent to the existence of an actually measurable set.
Thinking categorically, the answer is yes if and only if the monad is not isomorphic to the identity. Now, the codensity monad of a subcategory inclusion is isomorphic to the identity if and only if is codense in (by definition, if you choose your definitions right). So:
There exists a measurable set if and only if is NOT codense in .
This was first shown by Isbell back in 1960, in his paper “Adequate subcategories” (Theorem 2.5), though he proved it directly rather than going via monads.
So, a model of ETCS in which there are no measurable sets is one in which the countable sets play a special role: they are codense in the category of all sets.
A careful examination of the proof shows that the codensity monad of is unchanged if we replace by any full subcategory containing at least one infinite set. In particular, we could take to be the full subcategory consisting of the single set .
So what?
Well, if we replace by the full subcategory on then the description of in terms of natural transformations (or as an end) becomes something very simple, expressible without categorical language. It tells us that the set of ultrafilters on closed under countable intersections is in bijection with the set of -equivariant maps
By , I mean the monoid of all functions , with composition as the monoid operation. It acts on and in a natural way.
For example, the principal ultrafilter on an element corresponds to the -projection .
Putting this together, a set is countably measurable if and only if the projections are not the only -equivariant maps . Hence:
There exists a measurable set if and only if there exist a set and an -equivariant map that is not a projection.
David and I had a brief exchange about this theorem back in Part 1, apropos of some commentary by Lawvere.
All of this codensity stuff can be done with changed to the category of sets , for any fixed . The codensity monad of assigns to each set the set of -complete ultrafilters on . But that’s for a fixed . It’s hard to imagine any nontrivial way in which the assignment
could be functorial, let alone a monad.
That’s it for largeness conditions — I’m not going beyond measurable. It could be fun to carry on… For example, an uncountable set is strongly compact if every -complete filter on a set can be extended to an -complete ultrafilter, and it’s a nice but not so easy exercise to show that strongly compact implies measurable. (Rot-13ed hint: svefg fubj gung rirel fgebatyl pbzcnpg frg vf erthyne. Guvf vfa’g fb rnfl rvgure.) But enough! I’m stopping here.
Next time
Although I’m done with largeness conditions, I do want to say some things about the axiom scheme of replacement. Why? Because it implies several of the largeness conditions in earlier posts, because it’s historically important, because ETCS plus replacement is equivalent to ZFC, because it’s not widely enough known that there are versions of replacement that are entirely natural in structural set theory (it’s not tied to the membership-based approach), and because people seem to like talking about it. That’s for next time.
Re: Large Sets 11
So, in terms of the hierarchy that I described in part 9.5, your proof that measurables are inaccessible actually shows that they are 1-inaccessible, right? I wonder how much harder the proofs are that measurables are 2-inaccessible, hyper-inaccessible, or Mahlo.