The n-Category Café

Let’s recall the definition: an uncountable set $X$ is measurable if it admits a nonprincipal ultrafilter that is $X$-complete — in other words, closed under $I$-fold intersections for all $I \lt X$.

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 $X$ be a measurable set. To show that $X$ is inaccessible, we have to prove three things:

• $X$ is uncountable. This is an explicit part of the definition of measurability.

• $X$ is regular. In other words, it’s impossible to express $X$ as a union $\bigcup_{i \in I} X_i$ with $I \lt X$ and $X_i \lt X$ for all $i$.

  The key here is an observation about nonprincipal $X$-complete ultrafilters. Each member $A$ of such an ultrafilter must have cardinality $\geq X$: for if not, $A$ would be a union of $\lt X$ singletons, and since singletons aren’t in the ultrafilter, neither is $A$.

  Since $X$ is measurable, there is some nonprincipal $X$-complete ultrafilter $\mathcal{U}$ on it. If $(X_i)_{i \in I}$ is a family of subsets of $X$ with $I \lt X$ and $X_i \lt X$, then it follows from our observation that no $X_i$ belongs to $\mathcal{U}$. Since $I \lt X$, the union $\bigcup X_i$ is not in $\mathcal{U}$ either, so it definitely can’t be $X$.

• $X$ is a strong limit. In other words, if $Y \lt X$ then $2^Y \lt X$.

  This can be proved using a nice lemma: for sets $A$ and $B$, any ultrafilter on $B^A$ closed under both $A$- and $B$-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 $X$ and $Y$ be sets, suppose that $Y \lt X \leq 2^Y$, and let $\mathcal{U}$ be an $X$-complete ultrafilter on $X$. We’ll show that $\mathcal{U}$ is principal.

  For take an injection $i: X \to 2^Y$. Pushing $\mathcal{U}$ forward along $i$ gives an $X$-complete ultrafilter $i_\ast \mathcal{U}$ on $2^Y$. Then $i_\ast \mathcal{U}$ is closed under $Y$-fold intersection, so by the lemma, $i_\ast \mathcal{U}$ is principal. Since $i$ is injective, $\mathcal{U}$ 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 $X$, there exists an inaccessible set $\lt X$.

In fact, something much stronger is true:

For every measurable set $X$, there are $X$ isomorphism classes of inaccessible sets $\lt X$.

There certainly aren’t more than $X$ of them, for reasons that have nothing to do with largeness axioms: for any set $X$ whatsoever, there are at most $X$ iso classes of sets $\lt X$. So the force of the theorem is that there are as many as $X$ inaccessible sets smaller than any measurable set $X$.

This stronger result has a corollary:

For every measurable set $X$, there are unboundedly many inaccessibles $\lt X$.

That is, for any $Y \lt X$, there is some inaccessible set $Z$ with $Y \lt Z \lt X$. For if not, $Y$ would be an upper bound for the inaccessibles $\lt X$, so there would be at most $Y$ inaccessibles $\lt X$, 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 $\lt$ 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 $X$ there are $X$ 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 $X$, we have the set

$$K(X) = \{\text{iso classes of sets}\ \lt X \},$$

and the proof will construct an ultrafilter on $K(X)$ with the property that the set of inaccessible sets $\lt X$ belongs to the ultrafilter. This immediately implies that there’s at least one inaccessible set $\lt X$, as $\emptyset$ does not belong to any ultrafilter. In fact, the ultrafilter has properties implying that every member of it has cardinality $\geq X$, and this gives the full-strength result: there are $X$ iso classes of inaccessible sets $\lt X$.

So we won’t actually construct $X$ inaccessible sets $\lt X$. We’ll just show that there are that many of them.

I’ll now sketch a proof that when $X$ is measurable, there are $X$ isomorphism classes of inaccessible sets $\lt X$. It’s the argument you’ll find in some set theory texts, rewritten in a structural/neutral style. Here we go.

• Choose a nonprincipal $X$-complete ultrafilter $\mathcal{U}$ on $X$, which we can because $X$ is measurable.

• Define $K(X)^X/\mathcal{U}$ to be the set $K(X)^X$ quotiented by the equivalence relation that identifies two functions $X \to K(X)$ when their equalizer belongs to $\mathcal{U}$. (If you know about ultraproducts then you’ll recognize that this is one.) Write $[F]$ for the equivalence class of a function $F: X \to K(X)$.

• Define a relation $\lt$ on $K(X)^X/\mathcal{U}$ by $$[F] \lt [G] \ \iff\ \{x \in X: F(x) \lt G(x)\} \in \mathcal{U},$$ and check that this is well-defined.

• Show that $\lt$ is a well-order on $K(X)^X/\mathcal{U}$. Ultimately this is because cardinal inequality is a well-order on $K(X)$, 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 $a_0 \gt a_1 \gt \cdots$. The uncountability of $X$ is also needed in this step.

• Each $A \lt X$ gives rise to an element of $K(X)^X/\mathcal{U}$, namely, the equivalence class $[A]$ of the constant function $X \to K(X)$ with value $A$. Call such elements of $K(X)^X/\mathcal{U}$ constant.

• Show that in $K(X)^X/\mathcal{U}$, 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 $X$ and take the equivalence class of the function $x \mapsto \{ y \in X: y \lt x\}$.

• Since $K(X)^X/\mathcal{U}$ is well-ordered and not every element is constant, it has a least nonconstant element $[F]$. Then everything smaller than $[F]$ is constant.

• Push the ultrafilter $\mathcal{U}$ on $X$ forward along $F: X \to K(X)$ to give an ultrafilter $F_\ast \mathcal{U}$ on $K(X)$. Since $\mathcal{U}$ is $X$-complete, so is $F_\ast \mathcal{U}$. Since $[F]$ is not constant, $F_\ast \mathcal{U}$ is not principal.

• Show that:

  • the set of iso classes of uncountable sets $\lt X$ belongs to $F_\ast \mathcal{U}$;
  • the set of iso classes of strong limits $\lt X$ belongs to $F_\ast \mathcal{U}$;
  • the set of iso classes of regular sets $\lt X$ belongs to $F_\ast \mathcal{U}$.

  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 $\lt X$ belongs to $F_\ast \mathcal{U}$.

• Since $\mathcal{F}_\ast \mathcal{U}$ is a nonprincipal $X$-complete ultrafilter, every member has cardinality $\geq X$. But it’s an ultrafilter on $K(X)$, which is $\leq X$, so every member has the same cardinality as $X$. In particular, the set of iso classes of inaccessible sets $\lt X$ has cardinality $X$.

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 $\sigma$-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 $f: \mathbb{R} \to \mathbb{R}$ is a continuous function, then $f(B)$ is Lebesgue measurable for each Borel subset $B$ of $\mathbb{R}$. Now suppose that $f, g: \mathbb{R} \to \mathbb{R}$ are continuous functions. Is $f(\mathbb{R} \setminus g(B))$ Lebesgue measurable for each Borel set $B$? 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 $\mathbb{R}$ can be affected by the existence of a measurable set — which is necessarily much, much, bigger than $\mathbb{R}$.

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 $X$ (such as ultrafilters) and functions $2^X \to \{0, 1\}$ (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 $X$ and a $\{0, 1\}$-valued probability measure $\mu$ on $X$, defined on every subset of $X$. What kind of function $f: X \to Y$ on $X$ can we integrate against $\mu$? That is, when does the expression

$$\int_X f \ d\mu$$

define an element of $Y$ in some reasonable way?

Well, if $f$ is constant on some subset of $X$ of measure $1$ then the integral certainly makes sense: it should be the constant value of $f$. (Remember that $\mu$ is a probability measure: $\mu(X) = 1$.) Since $\mu$ is countably additive, this is guaranteed to happen when $Y$ is countable. So, $\mu$ determines an “integration” operator

$$\int_X - d\mu : \mathbf{Set}(X, Y) \to Y$$

for each countable set $Y$.

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 $X$ to be a family of maps

$$\Bigl(\alpha_Y: \mathbf{Set}(X, Y) \to Y\Bigr)_{\text{countable}\ Y}$$

natural in countable sets $Y$. Then the following three kinds of structure on $X$ are essentially the same, in the sense of being in bijection with one another:

• integration operators on $X$;

• $\{0, 1\}$-valued probability measures on $X$;

• ultrafilters on $X$ closed under countable intersection.

And now we get to something categorically significant. Write $T(X)$ for the set of integration operators on $X$. Then $T$ is a functor $\mathbf{Set} \to \mathbf{Set}$. In fact, it’s more than just a functor: it’s a monad, the codensity monad of the inclusion

$$\mathbf{Ctbl} \hookrightarrow \mathbf{Set}$$

of the category of countable sets into the category of sets.

If you like ends, you’ll find it enlightening to write $T(X)$ as one:

$$T(X) = \int_{Y \in \mathbf{Ctbl}} Y^{\Set(X, Y)}.$$

This is an instance of the general end formula for a codensity monad. Alternatively, the fact that $T$ is this codensity monad follows from the original definition of $T(X)$ as a set of natural transformations.

In summary, the codensity monad $T$ of $\mathbf{Ctbl} \hookrightarrow \mathbf{Set}$ assigns to each set $X$ the set of ultrafilters on $X$ closed under countable intersections. Some elements of $T(X)$ are trivial: there’s the principal ultrafilter $\mathcal{U}_x$ for each $x \in X$. And predictably, the unit $X \to T(X)$ of the monad is the assignment $x \mapsto \mathcal{U}_x$.

But the question is, are there ever any other elements of $T(X)$?

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 $T$ is not isomorphic to the identity. Now, the codensity monad of a subcategory inclusion $\mathbf{B} \hookrightarrow \mathbf{A}$ is isomorphic to the identity if and only if $\mathbf{B}$ is codense in $\mathbf{A}$ (by definition, if you choose your definitions right). So:

There exists a measurable set if and only if $\mathbf{Ctbl}$ is NOT codense in $\mathbf{Set}$.

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 $\mathbf{Ctbl} \hookrightarrow \mathbf{Set}$ is unchanged if we replace $\mathbf{Ctbl}$ by any full subcategory $\mathbf{C}$ containing at least one infinite set. In particular, we could take $\mathbf{C}$ to be the full subcategory consisting of the single set $\mathbb{N}$.

So what?

Well, if we replace $\mathbf{Ctbl}$ by the full subcategory on $\mathbb{N}$ then the description of $T$ 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 $X$ closed under countable intersections is in bijection with the set of $End(\mathbb{N})$-equivariant maps

$$\mathbb{N}^X \to \mathbb{N}.$$

By $End(\mathbb{N})$, I mean the monoid of all functions $\mathbb{N} \to \mathbb{N}$, with composition as the monoid operation. It acts on $\mathbb{N}$ and $\mathbb{N}^X$ in a natural way.

For example, the principal ultrafilter on an element $x \in X$ corresponds to the $x$-projection $\mathbb{N}^X \to \mathbb{N}$.

Putting this together, a set $X$ is countably measurable if and only if the projections are not the only $End(\mathbb{N})$-equivariant maps $\mathbb{N}^X \to \mathbb{N}$. Hence:

There exists a measurable set if and only if there exist a set $X$ and an $End(\mathbb{N})$-equivariant map $\mathbb{N}^X \to \mathbb{N}$ 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 $\mathbf{Ctbl}$ changed to the category $\mathbf{Set}_{\lt Y}$ of sets $\lt Y$, for any fixed $Y$. The codensity monad of $\mathbf{Set}_{\lt Y} \hookrightarrow \mathbf{Set}$ assigns to each set $X$ the set of $Y$-complete ultrafilters on $X$. But that’s for a fixed $Y$. It’s hard to imagine any nontrivial way in which the assignment

$$X \mapsto \{ X\text{-complete ultrafilters on}\ X \} = \int_{Y \lt X} Y^{\mathbf{Set}(X, Y)}$$

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 $X$ is strongly compact if every $X$-complete filter on a set can be extended to an $X$-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.