Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 10, 2021

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,)[0, \infty). We might as well rescale so that we’re dealing with probability measures. An initial, crude, question is:

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

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}\{0, 1\}.

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

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

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

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

such that μ(X)=1\mu(X) = 1 and μ( iA i)= iμ(A i)\mu(\coprod_i A_i) = \sum_i \mu(A_i) for all countable families (A i)(A_i) of pairwise disjoint subsets of XX?

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 00 or 11. But no one’s ever proved that it’s impossible.

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

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

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

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

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

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

𝒰={AX:μ(A)=1}. \mathcal{U} = \{A \subseteq X : \mu(A) = 1\}.

In other words, a subset of XX is in 𝒰\mathcal{U} if it has μ\mu-measure 11, and it’s not if it has μ\mu-measure 00.

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 XX, does there exist a nonprincipal ultrafilter on XX closed under countable intersections?

I’ll call a set XX 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 XX. We can think of the subsets of XX 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}\{n\} is small as 𝒰\mathcal{U} is not principal, but their union = n{n}\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 XX is never closed under XX-fold intersections. But it’s conceivable that a nonprincipal ultrafilter on XX could be closed under II-fold intersections for all I<XI \lt X.

There’s some terminology for this. Let XX and YY be sets. An ultrafilter on XX is YY-complete if it is closed under II-fold intersections for all I<YI \lt Y. Examples:

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

  • A principal ultrafilter is YY-complete for all sets YY. (Boring!)

  • An ultrafilter is closed under countable intersections if and only if it is 1\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, YY-complete means closed under II-fold intersections for II strictly less than YY. So although a set XX can’t admit a nonprincipal ultrafilter with XX-fold intersections, it could conceivably admit one that’s XX-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 XX, and let YY be another set. Then 𝒰\mathcal{U} is a YY-complete ultrafilter on XX if and only if every map from XX to a set <Y\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 XX is the same as an \mathbb{N}-complete ultrafilter, which is a collection 𝒰\mathcal{U} of subsets of XX with the following property: whenever f:XIf: X \to I is a map from XX into a finite set II, there is a unique iIi \in I such that f 1(i)𝒰f^{-1}(i) \in \mathcal{U}. Or put another way, whenever nn \in \mathbb{N} and X=X 1⨿⨿X nX = X_1 \amalg \cdots \amalg X_n, there is a unique ii such that X i𝒰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 XX-complete ultrafilter on a set XX is a collection 𝒰\mathcal{U} of subsets with the following property: whenever I<XI \lt X and f:XIf: X \to I, there is a unique iIi \in I such that f 1(i)𝒰f^{-1}(i) \in \mathcal{U}.

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

A set XX is measurable if it is uncountable and there exists a nonprincipal XX-complete ultrafilter on XX. 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.

Digression   The 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 are huge, 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. That terminology 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 XX is measurable if it is uncountable and admits a nonprincipal ultrafilter that’s XX-complete.

If XX 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 XX be the smallest countably measurable set. We’ve already noted that XX 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 XX that’s closed under countable intersections. We’re going to show that 𝒰\mathcal{U} is actually XX-complete. It’s enough to show that whenever f:XIf: X \to I is a function from XX to a set I<XI \lt X, some fibre of ff is in 𝒰\mathcal{U}. But the pushforward

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

is an ultrafilter on II closed under countable intersections, so by minimality of XX, it’s principal. That is, f 1(i)𝒰f^{-1}(i) \in \mathcal{U} for some iIi \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.

Posted at July 10, 2021 9:47 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3330

6 Comments & 0 Trackbacks

Re: Large Sets 10

Supposing it weren’t too late to replace measurable, what would be a good replacement? Some variation on ultrafiltrable, 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.

Posted by: Blake Stacey on July 11, 2021 8:30 PM | Permalink | Reply to this

Re: Large Sets 10

Interesting question. I agree, it should be beneficial to figure out what they should really be called.

There’s a similarly flavoured definition for groups called amenability. An amenable group is one that admits a finitely additive probability measure defined on all of its subsets and invariant under translation on one side. As I understand it, the name is a pun: amenable means agreeable or cooperative, but it also sounds like a-MEAN-able, and probability measures have something to do with means.

“Amenable set” might have been a decent name. Unfortunately, it conflicts with the group theory usage, since that involves finitely additive measures. And it still has the drawback that it sounds more like a smallness condition than a largeness condition.

Posted by: Tom Leinster on July 11, 2021 9:17 PM | Permalink | Reply to this

Re: Large Sets 10

Is there a version of the definition of measurable set that demands that all non principle ultrafilters be X complete.

I think understand the intuition behind this: the set is so large, that even if you interesect large subsets a whole lotta times. The result is still large. But I wonder if that is somehow tied to the notion of largeness (that is the non principle ultrafilter).

Posted by: Swill Stroganoff on July 11, 2021 8:55 PM | Permalink | Reply to this

Re: Large Sets 10

Is there a version of the definition of measurable set that demands that all non principle ultrafilters be X complete.

There might be something like this, but I don’t know of it.

The definition exactly as you state it wouldn’t be useful, as the ones satisfying your condition are just the countable sets.

Proof: let XX be an uncountable set. Choose any injection i:Xi: \mathbb{N} \to X and any nonprincipal ultrafilter 𝒰\mathcal{U} on \mathbb{N}. Push 𝒰\mathcal{U} forward along ii to get an ultrafilter i *𝒰i_\ast \mathcal{U} on XX. Since the ultrafilter 𝒰\mathcal{U} on the countable set \mathbb{N} is nonprincipal, it’s not closed under countable intersections, so i *𝒰i_\ast \mathcal{U} isn’t either. Since XX is uncountable, this implies that i *𝒰i_\ast \mathcal{U} is not XX-complete. Hence XX admits a nonprincipal ultrafilter that isn’t XX-complete.

It’s hard to visualize these things. If anyone has a good mental picture of more/less complete ultrafilters, I’d like to hear about it. I don’t.

Posted by: Tom Leinster on July 11, 2021 9:10 PM | Permalink | Reply to this

Re: Large Sets 10

Found a typo: I’ll [call] a set XX with this property countably measurable.

Posted by: Stéphane Desarzens on July 12, 2021 7:08 AM | Permalink | Reply to this

Re: Large Sets 10

Thanks — fixed.

Posted by: Tom Leinster on July 12, 2021 10:13 AM | Permalink | Reply to this

Post a New Comment