### Large Sets 9.5

#### Posted by Mike Shulman

*Previously: Part 9. Next: Part 10*

In the last comment thread, Tom invited me to write a post about some of the sizes of sets in between inaccessible sets and measurable sets. I’m not sure he was serious, but I’m going to take him up on it anyway. (-:

There are a lot of sizes of sets in between inaccessibles and measurables, but in this post I’ll just talk about “higher inaccessible” sets and Mahlo sets. I think these are worth thinking a bit about, especially as a followup to Tom’s very nice description of various kinds of large sets that are *smaller* than inaccessibles, because they can be thought of roughly as continuing the project of “making things that can’t be reached from below”. Measurable sets and their ilk feel to me like less of a straightforward continuation of that project, bringing in somewhat more exotic definitions that turn out to make them very large.

In addition, I hope to give a very fragmentary idea of how must *vastly bigger* than an inaccessible set a measurable set must be, by exploring just a bit of the terrain in between.

Some of the sizes of large sets that Tom introduced can be described roughly as “un-reachable from below by operations X”, where X often involves the assumed existence of smaller large sets. For instance, if beths exist (post 6), then the beth fixed points (post 7) are the sets that are un-reachable from below by constructing beths. Inaccessible sets are un-reachable from below by *any* of the other operations that Tom mentioned. But what about sets that are un-reachable from below *by constructing inaccessibles*?

In order to make “constructing inaccessibles” into an operation, consider the property that every set is smaller than some inaccessible. We then have an operation sending any set to the *smallest* inacessible that’s larger than it. A set is called **1-inaccessible** if it’s unreachable from below by this operation. More precisely, $X$ is 1-inaccessible if it is inaccessible and for any $A\lt X$, there is an inaccessible $B$ such that $A\lt B\lt X$. Thus, essentially by definition, we have

For any 1-inaccessible set $X$, there are unboundedly many inaccessible sets $\lt X$.

If $X$ is 1-inaccessible, then the collection of sets $\lt X$ model ETCS, and also model “every set is smaller than some inaccessible”. Thus, as before we have (assuming, as always, that ETCS is consistent):

It is consistent with ETCS + (every set is smaller than some inaccessible) that there are no 1-inaccessibles.

1-inaccessible sets are somewhat relevant to the modeling of type theory. When modeling ordinary type theory, we often assume there are a countable number of inaccessibles, to model a countable hierarchy of universes. This isn’t good enough if we want to state things about all of those universes, so sometimes we introduce an $\omega$th universe. And if we want to be able to use type theory to reason about *arbitrary* sets, it’s natural to assume that every set is contained in some universe, i.e. every set is smaller than some inaccessible.

Of course, putting an index “1” in front immediately leads us to the next generalization. A set is **2-inaccessible** if it is inaccessible and there are unboundedly many *1-inaccessibles* smaller than it. And it is **3-inaccessible** if it is inaccessible and there are unboundedly many 2-inaccessibles smaller than it. *Ad infinitum…*

What kind of *infinitum*? Well, we clearly get $n$-inaccessibles for all natural numbers $n$. We can then say a set is **$\omega$-inaccessible** if it is $n$-inaccessible for all natural numbers $n$. Then we can say it’s **$(\omega+1)$-inaccessible** if there are unboundedly many $\omega$-inaccessibles smaller than it. And **$(\omega+2)$-inaccessible** if there are unboundedly many $(\omega+1)$-inaccessibles smaller than it. *Ad infinitum…*

More generally, for any well-ordered set $W$, a set $X$ is **$W$-inaccessible** if it is inaccessible and for every well-ordered set $V\prec W$, there are unboundedly many $V$-inaccessibles smaller than $X$. So after $(\omega+n)$-inaccessibles we have $(\omega+\omega)$-inaccessibles, and so on to $\omega^2$-inaccessibles, $\omega^\omega$-inaccessibles, and so on. After exhausting the countable ordinals we have $\beth_1$-inaccessibles, $\beth_2$-inaccessibles, and so on. Then $W$-inaccessibles where $W$ is the smallest beth fixed point. Then $W$-inaccessibles where $W$ is the smallest inaccessible. Then $W$-inaccessibles where $W$ is the smallest 1-inaccessible.

If we aren’t tired yet, we can imagine a well-ordered set $W$ whose underlying set is itself $W$-inaccessible. According to wikipedia, some people call this a **hyper-inaccessible**; one might also call it an “inaccessibility fixed point”.

But, of course, we’re not done: we can consider an inaccessible set such that there are unboundedly many hyper-inaccessibles smaller than it, which we can call **1-hyper-inaccessible**. Then we have 2-hyper-inaccessibles, which have unboundedly many 1-hyper-inaccessibles smaller than them. And so on, until a $W$-hyper-inaccessible set (for some well-ordered set $W$) has unboundedly many $V$-hyper-inaccessibles smaller than it for every well-ordered set $V\prec W$. And, of course, a **hyper-hyper-inaccessible** set is the underlying set of a well-ordering $W$ that is itself $W$-hyper-inaccessible. It’s natural to expect to be able to define “hyper$^W$-inaccessibles” for any well-ordered set $W$, although I haven’t seen this written down.

I already find it kind of mind-blowing to think about how big these sets are. At first it seems like an inaccessible must be very large, especially after seeing how it’s bigger than all the kinds of large sets Tom discussed in parts 1-8. Then it seems like a 1-inaccessible must be unimaginably larger than that: not only are there an *inaccessible number* of inaccessible sets smaller than a 1-inaccessible $X$, there are $X$-many inaccessibles smaller than it! But 1-inaccessibles are just the beginning; with limit and “diagonalization” constructions we can quickly leap into incredibly larger and larger sets.

And yet, as always, once we can describe an operation that produces large sets, that same description gives us a way to leap beyond it. Define a set $X$ to be **Mahlo** if it is inaccessible and given any notion of “large set” such that there are unboundedly many large sets smaller than $X$, there exists an inaccessible $Y\lt X$ such that there are unboundedly many large sets smaller than $Y$.

To show how a Mahlo set is larger than all the ones we’ve seen so far, first let $A\lt X$ and call a set “large” if it is larger than $A$. Then there are certainly unboundedly many such sets smaller than $X$, so there is an inaccessible $Y$ such that, in particular, $A\lt Y\lt X$. Varying $A$, we see there are unboundedly many inaccessibles smaller than $X$, i.e. $X$ is 1-inaccessible.

But now, we can instead call a set “large” if (for some fixed $A$) it is larger than $A$ and inaccessible. Then by what we just proved, there are unboundedly many large sets smaller than $X$, so there is an inaccessible $Y$ such that $A\lt Y\lt X$ and there are unboundedly many inaccessibles sets smaller than $Y$. Hence $Y$ is 1-inaccessible, and so (varying $A$) we’ve just proven that $X$ is 2-inaccessible. Proceeding in this way, we can show that a Mahlo set is $W$-inaccessible for any well-ordered set $W$ (**Edit:** as long as $W$ is smaller than it is), and indeed also $W$-hyper-inaccessible for any $W$, and so on.

Are we done? Of course not! Now we can call a set $X$ **1-Mahlo** if it is inaccessible and given any notion of “large set” such that there are unboundedly many large sets smaller than $X$, there exists a *Mahlo* $Y\lt X$ such that there are unboundedly many large sets smaller than $Y$. Then we have 2-Mahlo sets, 3-Mahlo sets, $W$-Mahlo sets, $W$-hyper-Mahlo sets, etc. Wikipedia tells me that there is a notion of “greatly Mahlo” that’s presumably even larger than these, and so on.

And yet, despite how unimaginably large all of these sets must be, set theorists have come up with ways to describe sets that must be incomprehensibly larger than *all* of them. In fact, all these kinds of hyper-inaccessibles and Mahlos, as well as many sets even larger than them, are sometimes called “small large sets”. Next time Tom will tell us about measurable sets, which are the first kind of “*large* large set” – which are much, much larger than *all* of the small large sets!

## Re: Large Sets 9.5

Bravo! Thank you!