### Large Sets 7

#### Posted by Tom Leinster

*Previously: Part 6. Next: Part 8*

Given a well-ordered set $W$, there are at least two ways of manufacturing a plain, unadorned set. You can, of course, take the underlying set $U(W)$. But you can also take the beth $\beth_W$. How do they compare in size?

Let’s look at some of the first few cases, recalling that when $n$ is a natural number, $\beth_n$ means $\beth_W$ for the unique well-ordered set $W$ with $n$ elements.

$\beth_0$ is $\mathbb{N}$, the smallest infinite set, whereas $0$ is the empty set.

$\beth_1$ is the uncountable set $2^\mathbb{N}$, whereas $1$ is the well-ordered set with only one element.

$\beth_4 = 2^{2^{2^{2^{\mathbb{N}}}}}$ is probably bigger than any specific set used by 95% of mathematicians in a lifetime, whereas $4$ has, well, just four elements.

So comparing $\beth_W$ with $U(W)$ seems like racing an intercontinental ballistic missile against a snail — or more traditionally, a hare against a tortoise.

Unlike in the fable, our tortoise never *overtakes* the hare. But it’s
conceivable that it does keep *catching up*, only to fall behind again an
instant later. Moments when the tortoise catches the hare are called “beth
fixed points”, and they’re our topic for today.

We can begin to understand how the race looks by going through an inductive proof that the tortoise never overtakes the hare:

$\beth_W \geq U(W)$

for all well-ordered sets $W$. (Apparently our hare is called Beth.) To avoid distracting complications, I’ll assume in the proof that all beths exist.

This inductive proof splits into three cases, according to the three kinds of well-ordered set:

Suppose that $W$ is empty. Then $\beth_W \cong \mathbb{N}$ and $U(W) \cong \emptyset$. Obviously $\mathbb{N} \geq \emptyset$: the hare begins with a head start.

Suppose that $W$ is a successor, say $W = V^+$. Then $\beth_W = 2^{\beth_V} \gt \beth_V$. What about $U(W)$? If $W$ is finite then $U(W) \cong U(V) + 1$, but the increase by $1$ doesn’t make a difference: the tortoise $U(W)$ hasn’t even reached the starting point $\mathbb{N}$ of the hare. And if $W$ is infinite then $U(W) \cong U(V)$, so the tortoise stands still while the hare leaps ahead. Whether $W$ is finite or infinite, the hare’s lead over the tortoise gets bigger.

Finally, suppose that $W$ is a limit. Then $\beth_W$ is the smallest set such that $\beth_W \geq 2^{\beth_V}$ for all $V \prec W$. Now turning to the underlying sets, it

*can*happen that $U(W)$ is strictly larger than $\sup_{V \prec W} U(V)$ — for example, if $W$ is the smallest uncountable well-ordered set. But because there are well-ordered sets of every cardinality, $U(W)$ can’t be any larger than the*successor*of that supremum. I leave the remaining details of the induction to you, but the point is that when $W$ is a limit, $U(W)$*is*sometimes slightly bigger than $U(V)$ for all previous well-ordered sets $V$: the tortoise may, if it feels like it, take a small step forward.

A well-ordered set $W$ such that $\beth_W$ exists and is $\cong U(W)$ is
called a **beth fixed point**, and what I’ve said so far may make it seem
unlikely that there are any beth fixed points at all.

But there’s another way to look at things that makes the existence of beth fixed points much more plausible. To explain it, I’ll need to do a quick recap of some stuff on well-ordered sets that I wrote about at leisure in Part 3.

So: writing $\preceq$ for the usual preorder on well-ordered sets, a
well-ordered set $W$ is **initial** if it’s $\preceq$-least of its
cardinality (that is, $W \preceq W'$ for any
well-ordered set $W'$ such that $U(W) \cong U(W')$). For every set $X$,
there is an initial well-ordered set $I(X)$ with underlying set $X$, and
it’s unique up to isomorphism. This defines a left adjoint $I$ to the
underlying set functor $U$:

$I: (\mathbf{Set}, \leq) \rightleftarrows (\mathbf{WOSet}, \preceq): U.$

Both categories appearing in this adjunction are large preorders. In particular, $\mathbf{Set}$ isn’t the ordinary category of sets! Its objects are sets, there’s one map $X \to Y$ if $X \leq Y$, and there are no maps $X \to Y$ otherwise.

The adjunction $I \dashv U$ restricts to an equivalence

$I: (\mathbf{Set}, \leq) \rightleftarrows (\text{initial well-ordered sets}, \preceq): U.$

So, sets and initial well-ordered sets are interchangeable, as long as the only aspect of sets we’re interested in is cardinal inequality.

Now let $W$ be a beth fixed point:

$\beth_W \cong U(W).$

Then $W$ must be an *initial* well-order: for if $V$ is another
well-ordered set with $V \prec W$ and $U(V) \cong U(W)$, then

$\beth_V \lt \beth_W \cong U(W) \cong U(V) \leq \beth_V,$

giving a contradiction.

So the beth fixed points are certain *initial* well-ordered sets. And since
initial well-ordered sets are in canonical one-to-one correspondence with
sets, we might as well work with sets instead. In other words, define a
*set* $X$ to be a **beth fixed point** if $\beth_{I(X)}$ exists and

$\beth_{I(X)} \cong X.$

We’ve defined the property of being a “beth fixed point” for both sets and well-ordered sets. The two definitions hang together nicely. That is, a set $X$ is a beth fixed point if and only if the well-ordered set $I(X)$ is a beth fixed point. Equivalently, a well-ordered set $W$ is a beth fixed point if and only if it is initial and the set $U(W)$ is a beth fixed point.

One advantage of this reformulation is that it lets us use our pre-existing intuition about fixed points. Rather than looking for points of equality of the two operations

$\beth_\bullet, U: (\text{well-ordered sets}) \to (sets),$

we can look for fixed points of the single operation

$\beth_{I(-)}: (sets) \to (sets).$

And now our intuition kicks in! In a geometric context, given an operation $f: S \to S$ on some kind of space $S$, how might we look for fixed points of $f$? The simplest way is to choose a point $s_0$ and iterate:

$s_0, f(s_0), f(f(s_0)), \ldots.$

If we’re lucky, this sequence has a limit, $s$. If we’re doubly lucky, $f$ is continuous enough that it preserves this limit. Then $s$ is a fixed point of $f$.

Let’s see if we can construct a beth fixed point by this strategy. Again, to keep things simple, I’ll assume that all beths exist in our model. Choose your favourite set $X$, and consider the sequence $(B_n)_{n \in \mathbb{N}}$ of sets given by

$B_0 = X, \quad B_{n + 1} = \beth_{I(B_n)}.$

If this sequence has a supremum — call it $B$ — then it is in fact preserved by $\beth_{I(-)}$, by a little argument that I’ll skip. So, $B$ is then a beth fixed point!

For example, if we start at $X = \emptyset$, then

$B_0 = \emptyset, \quad B_1 = \beth_0 = \mathbb{N}, \quad B_2 = \beth_{I(\mathbb{N})} = \beth_\omega, \quad B_3 = \beth_{I(\beth_\omega)}, \ldots.$

And if the $B_n$s have a supremum, $B$, then it must actually be the
*smallest* beth fixed point.

We seem to have shown not only that a beth fixed point exists, but that
there’s an abundance of them, unboundedly many of them: given any set
$X$, we constructed a beth fixed point $B$ at least as big as $X$. However, the
argument only goes through *if* the sequence has a supremum (which in ETCS
is the same as saying that the sequence is defined). And this isn’t
guaranteed, as we’ll see.

But before that, let’s pause to ask:

What’s the point of all this?

Is there any reason to compare $\beth_W$ with $U(W)$, or to ask whether they’re ever the same, other than general curiosity?

I claim that there is, that we’re more or less *forced* to consider beth
fixed points as soon as we’ve accepted the idea of iterating the
power set construction.

What this comes down to is a general point about axiomatic set theory. Suppose, for instance, that we’re interested in ETCS plus certain other axioms. Then it’s natural to ask which sets are too large to be constructed or accessed using our axioms. More exactly, call a set $X$ “unreachable” if the sets $\lt X$ are a model of ETCS plus our other axioms. Then the question becomes, which sets are unreachable? Can we characterize them directly?

For example, if we’re considering ETCS alone with no further axioms, we saw in Part 2 that the “unreachable” sets are the strong limits. That is, a set $X$ is a strong limit if and only if the sets $\lt X$ are a model of ETCS.

Now, what about ETCS plus the axiom “all beths exist”? Which sets are unreachable with respect to this axiomatic system? The answer is the beth fixed points. In other words:

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

This provides a different motivation for the concept of beth fixed point, quite separate from hares and tortoises.

Here’s a proof of the “only if” direction. (I leave “if” to you.) Let $X$ be a beth fixed point. We have to show that the sets $\lt X$ are a model of ETCS + (all beths exist).

The first observation is this:

Every beth fixed point is an uncountable strong limit.

Indeed, the well-ordered set $I(X)$ is a limit, from which it follows that $\beth_{I(X)}$ is a strong limit. But $X \cong \beth_{I(X)}$, so $X$ is a strong limit; and uncountability is easy. Hence the sets $\lt X$ are a model of ETCS.

Now we have to show that in this model, all beths exist. In other words, given a well-ordered set $W$ such that $U(W) \lt X$, our task is to show that $\beth_W$ exists and is $\lt X$.

By adjointness, $U(W) \lt X$ implies that $W \prec I(X)$. Now $\beth_{I(X)}$ exists (that was part of the definition of $X$ being a beth fixed point), so $\beth_W$ exists, and it follows from the definition of the beths that $\beth_W \lt \beth_{I(X)}$. But $\beth_{I(X)} \cong X$, so $\beth_W \lt X$, as required.

From this result, we get a little independence theorem:

It is consistent with ETCS + (all beths exist) that there are no beth fixed points.

The proof follows a pattern that we’ve already seen a few times before. Take a model of ETCS + (all beths exist). Call a set in this model “small” if it is $\lt$ every beth fixed point. It follows from the result above that the small sets are a model of ETCS + (all beths exist), and by construction, this model contains no beth fixed points. QED!

One can also consider *aleph* fixed points, defined in the obvious
way. Since

$U(W) \leq \aleph_W \leq \beth_W,$

any beth fixed point is an aleph fixed point. Much of what I’ve written here about beth fixed points can be repeated for aleph fixed points. But I don’t have anything special to say about the aleph case, so I’ll stop here.

#### Next time

Some of cardinal arithmetic is “trivial”, in the sense that

$X + Y \cong X \times Y \cong \max(X, Y)$

for infinite sets $X$ and $Y$. Next time, I’ll talk about the part that isn’t. We’ll look at exponentiation, infinite sums and products, cofinality, and the division of sets into regular and singular. And I’ll mention a completely wrong intuition about cardinal arithmetic that I carried around with me for years.

## Re: Large Sets 7

One could probably get even larger cardinsls by postulating the existence of limit sets from iterating the beth fixed point endofunctor $X \mapsto \beth_{I(X)}$ in the same way that one did by iterating exponentiation by the booleans $X \mapsto 2^X$. And then one could postulate an endofunctor $X \mapsto F(X)$ that takes sets to a limit set of iterating $\beth_{I(X)}$, and the existence of fixed points of $F(X)$.

One could then postulate a family of endofunctors $G:\mathbb{N}\rightarrow (Set \rightarrow Set)$ where $G(0)(X) = 2^X$, $G(1)(X) = \beth_I(X)$, $G(2)(X) = F(X)$, and so forth, iteratively defined by repeating the procedure above for $G(n)(X)$ to get $G(n+1)(X)$.