### Large Sets 10

#### Posted by Tom Leinster

*Previously: Part 9.5. Next: Part 11*

The early decades of the 20th century saw the development not only of axiomatic set theory, but also of Lebesgue’s theory of integration and measure. At some point, the two theories met and gave birth to the notion of measurability for sets. Measurability is maybe the most appealing of the “large set” conditions: it’s important set-theoretically, natural categorically, and — true to its origins — continues to arise occasionally in actual analysis.

I’ll begin with the “problem of measure”. These days, we’re used to the
idea that a measure on a space is only going to assign a volume to *some*
of the subsets, not all of them. But when measure theory was just starting,
it must have been natural to ask — and people did ask! —
whether it might be possible to assign a volume to *all* subsets of a
space.

For simplicity, let’s stick to finite positive measures, so that every subset has volume in $[0, \infty)$. We might as well rescale so that we’re dealing with probability measures. An initial, crude, question is:

Q0.Given a set $X$, is there a probability measure on $X$ defined on all subsets of $X$?

This isn’t a good question yet, because there are ways to make the answer “yes” that are too easy. They all involve measures that give nonzero value to one or more singletons. If we exclude such measures, we do get a good question, and it’s one that’s been studied intensively.

However, we’re going to look at a simplified version of the question, in which the measure is required to take values in $\{0, 1\}$.

We still have some trivial cases to exclude. For each $x \in X$, the Dirac measure $\delta_x$ is defined on all subsets of $X$ (giving value $1$ to subsets containing $x$ and $0$ to those that don’t). And it takes values in $\{0, 1\}$. Let’s call the Dirac measures “trivial”.

Q1.Given a set $X$, is there a nontrivial probability measure on $X$ defined on all subsets of $X$ and taking values in $\{0, 1\}$?

In other words, apart from the Dirac measures, is there a function

$\mu: 2^X \to \{0, 1\}$

such that $\mu(X) = 1$ and $\mu(\coprod_i A_i) = \sum_i \mu(A_i)$ for all countable families $(A_i)$ of pairwise disjoint subsets of $X$?

If you were sceptical that there were any nontrivial probability measures
defined on the full power set of a set, you’ll be even more sceptical that
there could be such a measure with the *further* property that all subsets
have measure $0$ or $1$. But no one’s ever proved that it’s impossible.

We do know that it’s impossible for *certain* sets $X$. For example, no
such measure exists if $X$ is countable. For if $\mu$ is one then

$1 = \mu(X) = \sum_{x \in X} \mu(\{x\}),$

so $\mu(\{x\}) = 1$ for some $x \in X$, so $\mu$ is a Dirac measure. But
the question is, are there *some* sets $X$ for which such a $\mu$ exists?

Let’s translate the problem from measure-theoretic language into set-theoretic language. A function

$\mu: 2^X \to \{0, 1\}$

is the same thing as a set $\mathcal{U}$ of subsets of $X$: put

$\mathcal{U} = \{A \subseteq X : \mu(A) = 1\}.$

In other words, a subset of $X$ is in $\mathcal{U}$ if it has $\mu$-measure $1$, and it’s not if it has $\mu$-measure $0$.

For $\mu$ to be a *finitely additive* measure is equivalent to
$\mathcal{U}$ being an ultrafilter. For $\mu$ to be an *actual*,
countably additive, measure is equivalent to $\mathcal{U}$ being an
ultrafilter closed under countable intersections. And for $\mu$ to be
nontrivial (that is, not a Dirac delta) is equivalent to $\mathcal{U}$ not
being a principal ultrafilter.

In this language, Question 1 becomes:

Q1, restated.Given a set $X$, does there exist a nonprincipal ultrafilter on $X$ closed under countable intersections?

I’ll call a set $X$ with this property **countably measurable**.

Phrased like this, the countability condition sticks out like a sore
thumb. From a set-theoretic perspective, what’s so special about
*countable* intersections? Why not intersections of other cardinalities?

So let’s stop and think for a while about intersections of elements of an ultrafilter.

Take an ultrafilter $\mathcal{U}$ on a set $X$. We can think of the subsets of $X$ in $\mathcal{U}$ as “big” and those not in $\mathcal{U}$ as “small”. (Or you can say “measure-one” and “measure-zero”.) A subset is big if and only if its complement is small.

By definition, any ultrafilter is closed under finite intersections, but perhaps a more intuitive way to think about it is that a finite union of small sets is small. This is equivalent, by taking complements.

Similarly, an ultrafilter is closed under countable intersections if and only if a countable union of small sets is small. This doesn’t always happen. For example, take a nonprincipal ultrafilter $\mathcal{U}$ on $\mathbb{N}$. Each singleton $\{n\}$ is small as $\mathcal{U}$ is not principal, but their union $\mathbb{N} = \bigcup_n \{n\}$ is large. So $\mathcal{U}$ is not closed under countable intersections.

The same argument shows that a nonprincipal ultrafilter on *any* set $X$ is
never closed under $X$-fold intersections. But it’s conceivable that a
nonprincipal ultrafilter on $X$ could be closed under $I$-fold
intersections for all $I \lt X$.

There’s some terminology for this. Let $X$ and $Y$ be sets. An ultrafilter
on $X$ is **$Y$-complete** if it is closed under $I$-fold intersections for
all $I \lt Y$. Examples:

Every ultrafilter is $\mathbb{N}$-complete, by definition.

A principal ultrafilter is $Y$-complete for all sets $Y$. (Boring!)

An ultrafilter is closed under countable intersections if and only if it is $\aleph_1$-complete, again by definition. I think people sometimes say “$\sigma$-complete” instead, in a nod to the measure-theoretic use of “$\sigma$-algebra” etc.

A category theorist doing set theory has to get used to the fact that there
are lots of *strict* inequalities, whereas category theory gravitates towards the non-strict ones. In particular, $Y$-complete means closed under
$I$-fold intersections for $I$ *strictly* less than $Y$. So
although a set $X$ can’t admit a nonprincipal ultrafilter with $X$-fold
intersections, it could conceivably admit one that’s $X$-complete.

There’s another way of thinking about intersections in ultrafilters that turns out to be useful (and *is* categorically appealing).

Let $\mathcal{U}$ be a set of subsets of a set $X$, and let $Y$ be another set. Then $\mathcal{U}$ is a $Y$-complete ultrafilter on $X$ if and only if every map from $X$ to a set $\lt Y$ has a unique fibre belonging to $\mathcal{U}$. I don’t think this is obvious. The only way I know of proving “if” involves choosing an arbitrary well-ordering. But it’s true!

For example, a plain vanilla ultrafilter on $X$ is the same as an $\mathbb{N}$-complete ultrafilter, which is a collection $\mathcal{U}$ of subsets of $X$ with the following property: whenever $f: X \to I$ is a map from $X$ into a finite set $I$, there is a unique $i \in I$ such that $f^{-1}(i) \in \mathcal{U}$. Or put another way, whenever $n \in \mathbb{N}$ and $X = X_1 \amalg \cdots \amalg X_n$, there is a unique $i$ such that $X_i \in \mathcal{U}$.

This isn’t how the definition of ultrafilter is usually presented, but it’s a little exercise to show that it’s equivalent (a result due to Galvin and Horn).

Or for another example, an $X$-complete ultrafilter on a set $X$ is a collection $\mathcal{U}$ of subsets with the following property: whenever $I \lt X$ and $f: X \to I$, there is a unique $i \in I$ such that $f^{-1}(i) \in \mathcal{U}$.

Q2.Given a set $X$, does there exist a nonprincipal $X$-complete ultrafilter on $X$?

A set $X$ is **measurable** if it is uncountable and there exists a nonprincipal $X$-complete ultrafilter on $X$. So Q2 asks which sets are measurable.

As a sort of example, $\mathbb{N}$ admits a nonprincipal
$\mathbb{N}$-complete ultrafilter, since *all* ultrafilters are
$\mathbb{N}$-complete. So it would be measurable… except that measurable
sets are explicitly required to be uncountable.

DigressionThe name “measurable” is arguably not great, for several reasons.First, if I didn’t know otherwise, I’d think that

unmeasurability was the largeness property. “Unmeasurable” sounds wild, and “measurable” sounds tame and tractable. But in fact, the measurable sets arehuge, as we’ll see.Second, “measurable set” (or “measurable cardinal”) sits uncomfortably with the standard term “measurable space” to mean a set equipped with a $\sigma$-algebra of subsets.

Thatterminology isn’t great either, as the point is not that you can measure the space itself, but rather its subsets.Third, there’s Lawvere’s objection quoted by David in a comment to Part 1: “Actually, measurable cardinals are those which canNOT be measured by smaller ones…”

But the name has been established for nearly a century, so there’s little hope of changing it now.

By now I’ve given you two closely related definitions:

A set is

*countably measurable*if it admits a nonprincipal ultrafilter that’s closed under countable intersections.A set $X$ is

*measurable*if it is uncountable and admits a nonprincipal ultrafilter that’s $X$-complete.

If $X$ is measurable then it’s certainly countably measurable, immediately
from the definitions. The converse doesn’t *look* true, and assuming that
either kind of set exists at all, it actually *isn’t* true. (I won’t give
the proof.)

With that in mind, the following result is a surprise:

In a model of ETCS, there exists a countably measurable set if and only if there exists a measurable set.

“If” is trivial, since measurability is stronger than countable
measurability. It’s “only if” that’s interesting. It says that given the existence of a
merely *countably* measurable set, we can deduce the existence of an *actually*,
*fully*, measurable set.

The argument is a lot easier than you might imagine, and in fact proves a stronger result:

In a model of ETCS, if there is some countably measurable set then the smallest such set is measurable.

For let $X$ be the smallest countably measurable set. We’ve already noted that $X$ can’t be countable: so it’s uncountable, which is one part of the definition of measurability.

Now for the main part. Take some nonprincipal ultrafilter $\mathcal{U}$ on $X$ that’s closed under countable intersections. We’re going to show that $\mathcal{U}$ is actually $X$-complete. It’s enough to show that whenever $f: X \to I$ is a function from $X$ to a set $I \lt X$, some fibre of $f$ is in $\mathcal{U}$. But the pushforward

$f_\ast \mathcal{U} = \{ B \subseteq I : f^{-1}B \in \mathcal{U}\}$

is an ultrafilter on $I$ closed under countable intersections, so by minimality of $X$, it’s principal. That is, $f^{-1}(i) \in \mathcal{U}$ for some $i \in I$. Done!

With this established, we’re mostly going to forget about *countable*
measurability. It may have been the condition that launched the study of measurable sets, but the stronger condition of measurability is what’s most
important in set theory.

There’s quite a lot more I want to say about measurability, but this post is long enough already, so I’ll stop here.

#### Next time

In the next post, I’ll talk about how measurability compares to other largeness conditions we’ve met — especially inaccessibility. I’ll also explain what measurable sets have to do with codensity monads, which is related to the theme of measure versus integration.

## Re: Large Sets 10

Supposing it weren’t too late to replace

measurable,what would be a good replacement? Some variation onultrafiltrable,perhaps? Even if the current terminology is locked in “for historical reasons”, it might be helpful to think through how terminology ought to be chosen, since we’re always inventing more of it.