The n-Category Café

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.