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 6, 2021

Large Sets 9

Posted by Tom Leinster

Previously: Part 8. Next: Part 9.5

Today I’ll talk about inaccessibility. A set is said to be “inaccessible” if it cannot be reached or accessed from below using certain operations. We’ve seen this rough idea before — but which operations are the ones in play here, and what makes them especially interesting?

The definition is short and sweet: a set is inaccessible if it is uncountable, a strong limit, and regular. Let’s review what that means:

  • A set XX is a strong limit if Y<X2 Y<XY \lt X \implies 2^Y \lt X. That’s the most economical form of the definition, anyway. But an equivalent condition is maybe more illumnating: an uncountable strong limit is a set XX such that the sets <X\lt X are a model of ETCS.

  • A set XX is regular if whenever (X i) iI(X_i)_{i \in I} is a family of sets with I<XI \lt X and X i<XX_i \lt X for all ii, then iIX i<X\sum_{i \in I} X_i \lt X. Another way to say this: there’s no map out of XX whose codomain and fibres are all smaller than XX.

So, for a set to be inaccessible means that it’s unreachable from below in two different ways: by the constructions that ETCS provides, and by coproducts of a smaller number of smaller sets.

Some other perspectives on inaccessibility begin to suggest why it’s an important notion:

  • Every infinite set is either regular or a weak limit. In other words, every successor is regular (as we saw last time). This makes it natural to ask which sets are both regular and a weak limit. The uncountable such sets are called weakly inaccessible. Accessibility itself is the corresponding notion with “strong limit” in place of “weak limit”.

    (What I’m calling “inaccessible” used to be called “strongly inaccessible”, but I believe I’m following the dominant modern usage by dropping the “strongly”.)

  • We saw last time that regularity is a natural condition. Now regularity involves sums (coproducts) of sets. What if we change them to products? That is, call a set XX product-regular if whenever (X i) iI(X_i)_{i \in I} is a family of sets with I<XI \lt X and X i<XX_i \lt X for all ii, then X i<X\prod X_i \lt X. Which sets are product-regular? Certainly \mathbb{N} is, but what else?

    In fact, for uncountable sets, product-regularinaccessible. \text{product-regular} \iff \text{inaccessible}. This is another hint that inaccessibility is important.

Can I give you an example of an inaccessible set? No! Inaccessible sets — if they exist — are larger than anything we’ve contemplated before, and beyond the realm where we can just “write one down”.

Let’s dig into that claim.

The largest kinds of sets we’ve considered so far are the beth fixed points. As I’ll explain, every inaccessible set is a beth fixed point… but most beth fixed points aren’t inaccessible. (They’re “accessible”, I guess, but do people really say that?)

The proof that inaccessible sets are beth fixed points is really nice, so I’ll show it to you in full. It rests on a fact I mentioned in Part 7:

A set XX is a beth fixed point if and only if the sets <X\lt X are a model of ETCS + (all beths exist).

We’ll show that every inaccessible set XX satisfies this equivalent condition. The sets <X\lt X are certainly a model of ETCS, since XX is a strong limit. What we have to show, then, is that for every well-ordered set WW whose underlying set U(W)U(W) is <X\lt X, the beth W\beth_W exists and is <X\lt X. We do this by induction on WW:

  • If WW is empty then W\beth_W exists (it’s 0=\beth_0 = \mathbb{N}) and is <X\lt X since XX is uncountable.

  • If WW is a successor, say W=V +W = V^+, then by inductive hypothesis, V\beth_V exists and is <X\lt X. Now W\beth_W exists; it’s 2 V2^{\beth_V}, which is <X\lt X since XX is a strong limit.

  • If WW is a nonempty limit then by inductive hypothesis, V\beth_V exists and is <X\lt X for all VWV \prec W. Now W=sup VW V=sup wW w \beth_W = \sup_{V \prec W} \beth_V = \sup_{w \in W} \beth_{&#x21A1; w} where w={wW:w<w}&#x21A1; w = \{ w' \in W : w' \lt w \}. This is a supremum of sets <X\lt X indexed by U(W)<XU(W) \lt X, and is therefore <X\lt X since XX is regular.

What I like about this proof is that the three cases of the transfinite induction naturally use the three parts of the definition of inaccessibility: uncountability, the strong limit property and regularity.

So: every inaccessible set is a beth fixed point. But inaccessibility is a much stronger condition. The smallest beth fixed point (if it exists) is not inaccessible. Nor is the second-smallest, nor the third-smallest. In fact:

For any inaccessible set XX, there are unboundedly many beth fixed points <X\lt X.

This means that for any set Y<XY \lt X, there is some beth fixed point BB with YB<XY \leq B \lt X.

We can even construct such a BB, in some sense of “construct”:

  • Take our starting set YY, and put B 0=YB_0 = Y.

  • Form an initial well order I(B 0)I(B_0) with underlying set B 0B_0. Now XX is a beth fixed point, meaning that I(X)\beth_{I(X)} exists and is X\cong X. Since B 0<XB_0 \lt X, it follows that I(B 0)\beth_{I(B_0)} exists and is <X\lt X. Put B 1= I(B 0)B_1 = \beth_{I(B_0)}. Then from our starting set B 0<XB_0 \lt X, we’ve constructed a new set B 1<XB_1 \lt X.

  • Repeat this process to get a sequence of sets Y=B 0B 1B 2, Y = B_0 \leq B_1 \leq B_2 \leq \cdots, which are all <X\lt X.

  • This sequence has an upper bound, XX, so it has a least upper bound, BB, satisfying YBXY \leq B \leq X. Better still, BB is strictly smaller than XX: for XX is uncountable and regular, so it can’t be the supremum of the sequence (B n) n(B_n)_{n \in \mathbb{N}} of strictly smaller sets. So YB<XY \leq B \lt X. And finally, BB is a beth fixed point, as mentioned in Part 7.

This result gives us another little independence theorem:

It is consistent with ETCS + (there are unboundedly many beth fixed points) that there are no inaccessible sets.

The proof is the same old argument we keep on seeing. Take a model of ETCS with unboundedly many beth fixed points. Call a set “small” if it is <\lt every inaccessible set in the model. Then the previous result implies that the small sets form a model of ETCS with unboundedly many beth fixed points, in which there are no inaccessible sets.

Perhaps I should state that proof a little more carefully. If the original model contains no inaccessible sets, we’re done. If it does contain an inaccessible set, there’s a smallest one, XX. Then by the previous result, the sets <X\lt X (the “small sets”) are a model of ETCS + (there are unboundedly many beth fixed points) + (there are no inaccessible sets).

So if there are any inaccessible sets at all, they’re among the beth fixed points, but the smallest inaccessible set is bigger than the smallest beth fixed point.

Next time

In the next of my posts we’ll look at measurable sets. Measurability is the largest large set axiom I’ll talk about in this series, and it’s a nice one: it connects to both measurability in the sense of measure theory and codensity monads in category theory.

Added later: but first, Mike will talk about the size levels in between inaccessibility and measurability.

Posted at July 6, 2021 10:55 AM UTC

TrackBack URL for this Entry:

5 Comments & 1 Trackback

Re: Large Sets 9

Now seems like a good moment to cite Mike Shulman’s Set theory for category theory, both for this post in particular and the series of posts in general.

I didn’t want to talk about the connection between inaccessibility and Grothendieck universes, but if you’re interested, you can find that topic discussed in section 8 of Mike’s paper.

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

Re: Large Sets 9

This reference, which was “Inspired by Shulman (2008)”, may be of interest:

“Some proposals for the set-theoretic foundations of category theory”, by Lorenzo Malatesta, 2011

Posted by: Keith Harbaugh on July 7, 2021 1:08 PM | Permalink | Reply to this

Re: Large Sets 9

I’m surprised to hear you’re going to skip right from inaccessibles to measurables. There are lots of sizes of sets in between those, like Mahlos and weakly compacts.

Posted by: Mike Shulman on July 7, 2021 2:34 PM | Permalink | Reply to this

Re: Large Sets 9

If you move fast, you can post a “Large Sets 9.5” on Mahlo and weakly compact sets before I put up Large Sets 10 :-)

There are also lots of sizes above measurable that I’m not going to discuss.

In this series, I’m just talking about the things I happen to find interesting and know (a little) about. That might mean it’s an idiosyncratic selection. Still, it looks like I’m going to get up to 12 posts, which is probably enough.

Posted by: Tom Leinster on July 7, 2021 4:58 PM | Permalink | Reply to this

Re: Large Sets 9

An accessible introduction of inaccessible sets ;)

Posted by: Stéphane Desarzens on July 7, 2021 6:07 PM | Permalink | Reply to this
Read the post Large Sets 9.5
Weblog: The n-Category Café
Excerpt: On hyper-inaccessible and Mahlo sets
Tracked: July 8, 2021 4:55 AM

Post a New Comment