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 $X$ is a strong limit if $Y \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 $X$ such that the sets $\lt X$ are a model of ETCS.

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

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 $X$ product-regular if whenever $(X_i)_{i \in I}$ is a family of sets with $I \lt X$ and $X_i \lt X$ for all $i$, then $\prod X_i \lt X$. Which sets are product-regular? Certainly $\mathbb{N}$ is, but what else?

In fact, for uncountable sets, $\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 $X$ is a beth fixed point if and only if the sets $\lt X$ are a model of ETCS + (all beths exist).

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

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

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

• If $W$ is a nonempty limit then by inductive hypothesis, $\beth_V$ exists and is $\lt X$ for all $V \prec W$. Now $\beth_W = \sup_{V \prec W} \beth_V = \sup_{w \in W} \beth_{↡ w}$ where $↡ w = \{ w' \in W : w' \lt w \}$. This is a supremum of sets $\lt X$ indexed by $U(W) \lt X$, and is therefore $\lt X$ since $X$ 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 $X$, there are unboundedly many beth fixed points $\lt X$.

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

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

• Take our starting set $Y$, and put $B_0 = Y$.

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

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

• This sequence has an upper bound, $X$, so it has a least upper bound, $B$, satisfying $Y \leq B \leq X$. Better still, $B$ is strictly smaller than $X$: for $X$ is uncountable and regular, so it can’t be the supremum of the sequence $(B_n)_{n \in \mathbb{N}}$ of strictly smaller sets. So $Y \leq B \lt X$. And finally, $B$ 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, $X$. Then by the previous result, the sets $\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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3328

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

Re: Large Sets 9

There’s an aspect of inaccessibility that I don’t understand. Can anyone help?

Some largeness conditions on a set $X$ can be understood as conditions on the full subcategory of sets $\lt X$. For example, whenever $X$ is an infinite set:

• $X$ is a weak limit $\iff$ the category of sets $\lt X$ has successors;

• $X$ is a strong limit $\iff$ the category of sets $\lt X$ has power sets;

• $X$ is an uncountable strong limit $\iff$ the category of sets $\lt X$ is a model of ETCS;

• $X$ is a beth fixed point $\iff$ the category of sets $\lt X$ has beths.

Is there any way of filling in the following blank?

• $X$ is inaccessible $\iff$ the category of sets $\lt X$ is/has [SOMETHING].

An inaccessible set is an uncountable strong limit that’s also regular, and it’s regularity that’s the problem here. For $X$ to be regular means there’s no map out of $X$ whose codomain and fibres are all $\lt X$, but in order to say that, we have to refer to $X$ itself — which obviously is not $\lt X$.

I initially assumed that my inability to fill in this blank was just a sign of my own limitations. That’s still a strong possibility. But now I’m thinking that maybe the blank can’t be filled in, and maybe that’s somehow the whole point of inaccessibility. I don’t know!

So, my questions are: is there a way of filling in the blank? Or is there some reason in principle why the blank cannot be filled in? Or even a proof that it can’t be?

Posted by: Tom Leinster on August 26, 2021 11:28 AM | Permalink | Reply to this

Re: Large Sets 9

I wonder if this relates back to the earlier discussion about co-completeness and ETCS. In ZFC, an inaccessible cardinal corresponds to a Grothendieck universe. Thus your question would seem to come down to the difference between a model of ETCS and a Grothendieck universe. And I think that this may have something to do with co-completeness, in the same sense as the earlier discussion.

Thus I’d guess that one might be able to say something like “the category of sets $\lt X$ is a model of ETCS and has (certain) large colimits”. Not sure off the top of my head what the exact statement would be, though, or how that directly relates to the definition of regularity as you gave it.

Posted by: Richard Williamson on August 26, 2021 12:22 PM | Permalink | Reply to this

Re: Large Sets 9

Yes, I know what you mean. What we want to say is that $X$ is regular iff the category of sets $\lt X$ has $I$-fold coproducts for every $I \lt X$. The obstacle is that in ETCS, we can’t specify an indexed family of sets without specifying its coproduct.

Posted by: Tom Leinster on August 26, 2021 12:36 PM | Permalink | Reply to this

Re: Large Sets 9

Hmm, the problem with constructing an arbitrary diagram out of $\mathbb{N}$ in ETCS as I had understood it is essentially that ETCS has no set of sets inside it: no ‘universe’ of small sets. But I don’t immediately see that this kind of objection applies here. If we are looking at sets of size less than $X$ for some set $X$, then $X$ plays the role of that ‘universe’.

Indeed, suppose that we wish to construct an $I$-indexed diagram of sets of size less than $X$, where $I$ is any set (viewed as a discrete category). Arbitrary unions of subsets of a given set exist in ETCS, so we can construct the union of the $X_i$’s viewed as subsets of $X \times I$, identifying $X_i$ with $X_i \times \{ i \}$. This union (which is disjoint!) maps canonically to $I$, giving us the desired $I$-indexed diagram. And once we have the $I$-indexed diagram, we can construct the colimit (i.e. coproduct) of it as a set in ETCS (but of course there is no reason to expect it to be a subset of $X$).

Thus, to me, it would seem to make perfect sense to say: $X$ is inaccessible if and only if the following two things hold:

1. the category of sets $\lt X$ is a model of ETCS;

2. for every set $I \lt X$, and every map $d : I \rightarrow 2^{X}$, the coproduct of the sets $d(i)$ for $i \in I$ (which always exists in ETCS for the reason discussed above!) in fact is smaller than $X$.

It could well be that I’m confused about something, but this is the kind of thing I had in mind.

Posted by: Richard Williamson on August 27, 2021 12:48 AM | Permalink | Reply to this

Re: Large Sets 9

Thanks — I agree with all that. However, it doesn’t answer the question as I intended it, because your condition (2) refers to $X$. When I wrote about filling in the blank here —

• $X$ is inaccessible $\iff$ the category of sets $\lt X$ is/has [SOMETHING]

— I intended “something” to be a property that doesn’t mention $X$, like the other properties in my bulleted list.

The question is whether it’s possible to characterize inaccessibility of $X$ in terms of the abstract category of sets $\lt X$. In other words, if I choose a set $X$ in secret and tell you only the category of sets $\lt X$, up to equivalence, can you figure out whether or not $X$ is inaccessible?

Along the same lines, here’s a completely precise version of the question. Let $\mathcal{S}$ and $\mathcal{T}$ be categories satisfying the ETCS axioms, and let $X \in \mathcal{S}$, $Y \in \mathcal{T}$. Write $\mathcal{S}_{\lt X}$ for the full subcategory of $\mathcal{S}$ consisting of the objects (sets) $\lt X$, and similarly $\mathcal{T}_Y$. Is it true that if $\mathcal{S}_{\lt X} \simeq \mathcal{T}_{\lt Y}$ then $X$ is inaccessible iff $Y$ is inaccessible?

Posted by: Tom Leinster on August 27, 2021 1:16 AM | Permalink | Reply to this

Re: Large Sets 9

Ah, I see, thanks!

Could one not simply say: the category of sets $\lt X$ must have all coproducts indexed by its objects? Not very category-theoretic to make use of the fact that the objects of a category are sets, but one could equally well formulate the same kind of assertion for any category equipped with a functor to sets, for instance, which looks a bit more ‘category theoretic’. One will have to use some kind of ‘reflexivity’ I think, i.e. one will have to have a statement which involves extracting some sets from the innards of one’s category, as otherwise there is surely no way to impose any ‘size restriction’ without speaking of $X$.

As an aside, I found myself wondering what would happen if one simply said: the category of sets $\lt X$ must have all coproducts (for diagrams in it which can be formulated in ETCS). Maybe this leads to some kind of Russell/Girard type paradox/contradiction. But it’s not immediately obvious to me, because which diagrams we can form is heavily tied to which large sets we have. If the category of sets $\lt X$ is a model of ETCS, then I think maybe this definition would force $X$ to be inaccessible, and indeed characterise $X$ as the largest inaccessible set in our ETCS. I’m not quite sure though.

Posted by: Richard Williamson on August 27, 2021 11:39 PM | Permalink | Reply to this

Re: Large Sets 9

the category of sets $\lt X$ must have all coproducts indexed by [the images of] its objects [under a] functor to sets

Since the functor $\mathcal{S}\to \mathrm{Set}$ is $\mathrm{Hom}_{\mathcal{S}}(1,-)$, this isn’t very different from saying “coproducts indexed by its hom-sets” as I did. It’s clearly implied by it, and the converse also holds when $X$ is a strong limit so that $\mathcal{S} = \mathrm{Set}_{\lt X}$ models ETCS.

what would happen if one simply said: the category of sets $\lt X$ must have all coproducts

In ETCS with classical logic, you’ll run into Freyd’s paradox.

Posted by: Mike Shulman on August 28, 2021 4:15 PM | Permalink | Reply to this

Re: Large Sets 9

this isn’t very different from saying “coproducts indexed by its hom-sets” as I did.

In ETCS with classical logic, you’ll run into Freyd’s paradox.

Freyd’s paradox was one of the possible paradoxes I had in mind. It is not clear to me that it applies here, though. From the point of view of the proof on the nLab page, I don’t immediately see a reason in general for the coproduct in question (over the set of arrows of a category, or indeed this set itself) to be definable in ETCS. I don’t think that adding in universes solves the issue; one will always have the same issue for sets larger than the largest universe one has.

The idea is that:

1. If we have a coproduct which exists in ETCS, then there must be some bounding set in our ETCS for all of the sets involved in the coproduct.
2. Moreover, if all the sets in the coproduct are $\lt X$ for some $X$, and the coproduct exists, then that bounding set must be $\lt X$.

Thus, saying that some category $\lt X$ has all coproducts (necessitating that they are definable) seems to be equivalent to saying that for any set of subsets of $X$ which has a bounding set in ETCS, this bounding set is in fact of size $\lt X$. This would imply that $X$ is at least the size of the largest inaccessible cardinal in ETCS. So if this category is in fact a model of ETCS, then $X$ must actually be the largest inaccessible cardinal in ETCS.

Now, it might well be that the statement

for any set of subsets of $X$ which has a bounding set in ETCS, this bounding set is in fact of size $\lt X$.

Posted by: Richard Williamson on September 6, 2021 10:53 AM | Permalink | Reply to this

Re: Large Sets 9

Inside of ETCS you can do all of ordinary mathematics as long as you don’t use replacement, and Freyd’s paradox requires only ordinary mathematics. To be a bit more specific, since ETCS doesn’t have dependent types, the only way to define a “category” is with a set of objects and a set of arrows. Thus in particular there is a set of arrows, and the coproduct of a constant family of sets indexed by that set (as used in Freyd’s paradox) certainly exists — it’s just the product of the constant object by the indexing set.

Posted by: Mike Shulman on September 7, 2021 9:59 AM | Permalink | Reply to this

Re: Large Sets 9

Hmm, when Tom wrote ‘category of sets $\lt X$’ I was interpreting that notion of ‘category’ as being foundation agnostic. It could be in ETCS, but not (necessarily) the same ETCS as we are otherwise working in when discussing large cardinals. This is very relevant for the point I am making, because if one has that set of arrows in one’s ETCS, then I agree of course that the proof of Freyd goes through; my point is specifically about the case where the largest set $X$ one has in some version $V$ of ETCS is some inaccessible cardinal, and where one looks at the category (not defined in the same ETCS!) of sets $\lt X$ in $V$.

In particular, to get to the heart of the size questions, one can I think, as I suggested, mostly ignore thinking about categories, and just consider whether the following statement is necessarily contradictory in ETCS.

for any set of subsets of $X$ which has a bounding set in $V$, this bounding set is in fact of size $\lt X$.

Posted by: Richard Williamson on September 7, 2021 1:10 PM | Permalink | Reply to this

Re: Large Sets 9

In any world where “the category of sets $\lt X$” is a category, it has a set of arrows. And if it “has all coproducts” in that world, then it has coproducts indexed by its set of arrows, and Freyd’s antinomy applies.

Regarding bounding sets, if I understand correctly what you mean by “bounding set”, then $X$ itself is a bounding set for the set of all subsets of $X$, but is not of size $\lt X$.

Posted by: Mike Shulman on September 8, 2021 4:49 PM | Permalink | Reply to this

Re: Large Sets 9

I don’t think inaccessibility of $X$ corresponds to any elementary property of the category of sets $\lt X$. But it can be phrased as a non-elementary property of that category, namely that that category (is a model of ETCS and) has coproducts indexed by its hom-sets. The latter is meant in the usual sense of category theory rather than the internal sense of this category being indexed over itself, so it is a nontrivial property. But it is invariant under equivalence, so it answers this version of the question:

if I choose a set $X$ in secret and tell you only the category of sets $\lt X$, up to equivalence, can you figure out whether or not $X$ is inaccessible?

But it doesn’t answer this version:

Let $\mathcal{S}$ and $\mathcal{T}$ be categories satisfying the ETCS axioms, and let $X \in \mathcal{S}$, $Y \in \mathcal{T}$. Write $\mathcal{S}_{\lt X}$ for the full subcategory of $\mathcal{S}$ consisting of the objects (sets) $\lt X$, and similarly $\mathcal{T}_Y$. Is it true that if $\mathcal{S}_{\lt X} \simeq \mathcal{T}_{\lt Y}$ then $X$ is inaccessible iff $Y$ is inaccessible?

at least, assuming that by “$X$ is inaccessible” you meant “$X$ is inaccessible in $\mathcal{S}$”. If we’re talking about inaccessibility of an object of some model $\mathcal{S}$ of ETCS, then when I said “coproducts indexed by its hom-sets” above that has to be interpreted in terms of $\mathcal{S}$-indexed categories, and so it would only transfer across an equivalence of indexed categories. But $\mathcal{S}_{\lt X}$ is an $\mathcal{S}$-indexed category while $\mathcal{T}_{\lt Y}$ is a $\mathcal{T}$-indexed category, and if $\mathcal{S}\neq \mathcal{T}$ it doesn’t even make sense to ask whether $\mathcal{S}_{\lt X} \simeq \mathcal{T}_{\lt Y}$ as indexed categories.

This is related to the point I made here about first-order versus second-order replacement. If you replace “inaccessible” with “worldly” then the answer to your question is yes, essentially by definition: $X$ is worldly iff $\mathcal{S}_{\lt X}$ is a model of ETCS+R. The extra second-order strength of inaccessibility beyond worldliness refers, I believe irreducibly, to sets outside $\mathcal{S}_{\lt X}$, so I don’t think it can be phrased in terms of elementary properties of $\mathcal{S}_{\lt X}$.

Posted by: Mike Shulman on August 27, 2021 5:34 PM | Permalink | Reply to this

Re: Large Sets 9

I don’t think inaccessibility of $X$ corresponds to any elementary property of the category of sets $\lt X$.

OK, good to know that you share that feeling. I wonder whether it can be expressed as a theorem.

Posted by: Tom Leinster on August 28, 2021 10:13 PM | Permalink | Reply to this

Re: Large Sets 9

I expect we just need to find the right way to phrase the question so that ZFC-theorists can match it up with something they know.

Posted by: Mike Shulman on August 30, 2021 4:29 PM | Permalink | Reply to this

Post a New Comment