## June 24, 2021

### Large Sets 6

#### Posted by Tom Leinster

Previously: Part 5. Next: Part 7

The plan for this series is to talk about ever larger sets and ever stronger axioms. So far we’ve looked at weak limits, strong limits, and alephs. Today we’ll look at beths.

The beths are the sets you get if you start with $\mathbb{N}$ and repeatedly take power sets. They are

$\beth_0 = \mathbb{N}, \ \beth_1 = 2^\mathbb{N}, \ \beth_2 = 2^{2^{\mathbb{N}}}, \ \ldots$

“and so on”, with one set $\beth_W$ for each well-ordered set $W$. The symbol $\beth$ is beth, the second letter of the Hebrew alphabet, after aleph. And like the alephs, the beths aren’t all guaranteed to exist.

Let’s dive straight in with an inductive definition. Take a well-ordered set $W$. Then $\beth_W$ is said to exist if $\beth_V$ exists for all well-ordered sets $V \prec W$ and there is some infinite set $X$ such that $2^{\beth_V} \leq X$ for all $V \prec W$. In that case, $\beth_W$ is defined to be the smallest such set $X$.

To digest this definition, it helps to think about the three different kinds of well-ordered set. These are:

• The empty well-ordered set.

• Successors. These are the well-ordered sets that can be expressed as $V^+$ for some other well-ordered set $V$. (Recall that $V^+$ means $V$ with a new greatest element adjoined.) The successors can also be characterized as the well-ordered sets with a greatest element.

• Limits. These are the well-ordered sets that are not successors. There seems not to be agreement over whether the empty well-ordered set should count as a limit; I haven’t acquired an opinion on this yet, but I’d be happy to be told what my opinion should be. Anyway, they’re the (nonempty?) well-ordered sets with no greatest element.

The corresponding beths look like this.

• Taking $W$ to be the empty well-ordered set $0$ in the definition of beth tells us that $\beth_0$ does exist, and that it’s the smallest infinite set — namely, $\mathbb{N}$. The sole reason why the word “infinite” is in the definition of beth is to make $\beth_0$ be equal to $\mathbb{N}$ rather than $\emptyset$. That’s just convention; I see no compelling reason to begin the beths at $\mathbb{N}$ rather than $\emptyset$.

• Suppose that $W$ is a successor, say $W = V^+$. If $\beth_V$ exists then $\beth_W$ also exists, with $\beth_W = 2^{\beth_V}$.

• Suppose that $W$ is a limit. In order for $\beth_W$ to exist, it must certainly be the case that $\beth_V$ exists for all $V \prec W$. That doesn’t guarantee that $\beth_W$ exists, but if it does, it’s the least upper bound of these sets $\beth_V$: $\beth_W = \sup_{V \prec W} \beth_V.$

For example,

$\beth_0 = \mathbb{N}, \ \beth_1 = 2^\mathbb{N}, \ \beth_2 = 2^{2^{\mathbb{N}}}, \ldots.$

Here $\beth_n$ means $\beth_{\mathbf{n}}$, where $\mathbf{n}$ is the unique $n$-element well-ordered set. And $\beth_\omega$, if it exists, is the supremum of $\beth_0, \beth_1, \ldots$.

This inductive definition of the beths is slightly tricky, in that it’s simultaneously an inductive definition of the existence of $\beth_W$ and of what the set $\beth_W$ actually is. Here’s a non-inductive alternative.

The idea is that if $\beth_W$ exists then we should be able to directly characterize the family of sets

$(\beth_V)_{V \preceq W},$

the last member of which is $\beth_W$ itself. Now I’ve been a bit slack in the indexing here, because it should really be over the isomorphism classes of well-ordered sets $V \preceq W$. But that’s easily overcome: every well-ordered set $V \preceq W$ is isomorphic to

$↡ w = \{ v \in W : v \lt w \}$

for a unique $w \in W^+$. So strictly speaking, our family is

$(\beth_{↡ w})_{w \in W^+}.$

And in ETCS, families are expressed as maps into the indexing set, so the picture is this:

Formally, let $W$ be a well-ordered set. Then $\beth_W$ exists if and only if there exist a set $E$ and a function $p: E \to W^+$ with the following property:

for all $w \in W$, the fibre $p^{-1}(w)$ is the least infinite set $\geq 2^{p^{-1}(v)}$ for all $v \lt w$.

In that case, $E$ and $p$ are determined uniquely up to isomorphism, and $\beth_W$ is defined as the fibre over the greatest element of $W^+$.

If all this seems rather familiar, it should! I gave a precisely analogous characterization of $\aleph_W$ rather than $\beth_W$ last time, with $p^{-1}(w) \gt p^{-1}(v)$ in place of $p^{-1}(w) \geq 2^{p^{-1}(v)}$.

Generally, if we write $Y \gg X$ to mean $Y \geq 2^X$, then the difference between the alephs and the beths is the difference between $\gt$ and $\gg$. Since $Y \gt X$ if and only if $Y \geq X^+$, this is another way of expressing the thought that the alephs are to the beths as $(\ )^+$ is to $2^{(\ )}$.

With this in mind, it’s easy to see that

$\aleph_W \leq \beth_W$

for all well-ordered sets $W$. More exactly, if $\beth_W$ exists then so does $\aleph_W$ and the inequality is true. If the generalized continuum hypothesis holds ($X^+ = 2^X$ for all infinite sets $X$) then the alephs and the beths are the same, but of course it needn’t hold.

Let’s now consider the existence of all beths, rather than individual ones. In other words, let’s think about the possible additional axiom:

$\beth_W$ exists for every well-ordered set $W$.

There’s an equivalent way of saying this that’s not inductive and doesn’t mention order either:

For all sets $I$, there exists a function $p: E \to I$ into $I$ such that for all distinct $i, j \in I$, either $2^{p^{-1}(i)} \leq p^{-1}(j)$ or $2^{p^{-1}(j)} \leq p^{-1}(i)$.

Again, this is an analogue of something I already said for the alephs, but with the relation $2^X \leq Y$ in place of $X \lt Y$.

As David Roberts pointed out in a comment in the context of the alephs, proving that this condition is equivalent to the existence of all beths isn’t completely trivial. The more tricky direction is to show that if this condition holds then all beths exist. For example, suppose you want to show that $\beth_\omega$ exists. It’s not enough to take $I$ to be the underlying set $\mathbb{N}$ of $\omega$, since the fibres could all be finite. You have to use an uncountable $I$. I don’t want to give the impression that the proof is hard — it’s not! — but I’m going to leave it to your imagination.

Let’s come back now to $\beth_\omega$. We saw that, if it exists, it’s the supremum of

$\beth_0 = \mathbb{N},\ \beth_1 = 2^{\mathbb{N}},\ \beth_2 = 2^{2^{\mathbb{N}}}, \ldots.$

But also, $\beth_\omega$ exists if and only if the coproduct

$\mathbb{N} + 2^\mathbb{N} + 2^{2^\mathbb{N}} + \cdots$

exists, and in that case, $\beth_\omega$ is this coproduct. The supremum is the same as the sum!

This becomes clear if you stare at this picture for long enough:

Got it? Let me say it in boring old words. Suppose that $\beth_\omega$ exists. Then the set $E$ shown can be constructed as a subset of $\mathbb{N} \times \beth_\omega$. And in fact, $\mathbb{N} \times \beth_\omega \cong \beth_\omega$, since $\mathbb{N} \leq \beth_\omega$. Hence the coproduct exists and is $\leq \beth_\omega$. Conversely, suppose that the coproduct exists; call it $S$. Then $S$ is certainly an upper bound of $\beth_0, \beth_1, \ldots$, so these sets have a least upper bound and it’s $\leq S$. Hence $\beth_\omega$ exists and is $\leq S$. That proves that the supremum is the same as the sum, and it shows that the total space $E$ in the diagram is exactly $\beth_\omega$.

Everything I’ve just said about $\omega$ is equally true for every limit well-ordered set $W$:

$\beth_W = \sup_{V \prec W} \beth_V = \sum_{V \prec W} \beth_V.$

And the argument is the same too. The step “$\mathbb{N} \leq \beth_\omega$” in the case $W = \omega$ gets replaced by the general fact that $U(W) \leq \beth_W$, where $U$ means underlying set. This follows from the chain of inequalities

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

both of which I mentioned before.

In fact, we met $\beth_\omega$ before in Part 2, although I only mentioned its name in passing. It is the smallest uncountable strong limit. More exactly, in a model of ETCS, $\beth_\omega$ exists if and only if an uncountable strong limit exists, and in that case the smallest uncountable strong limit is $\beth_\omega$.

Why is $\beth_\omega$ a strong limit? You should be able to persuade yourself that if a well-ordered set $W$ is a limit then the set $\beth_W$ is a strong limit (recalling what this means: if $X \lt \beth_W$ then $2^X \lt \beth_W$). In particular, the well-ordered set $\omega$ is a limit, so the set $\beth_\omega$ is a strong limit.

Since uncountable strong limits are not guaranteed to exist in a model of ETCS, and $\beth_\omega$ is an uncountable strong limit, we can deduce:

It is consistent with ETCS that $\beth_\omega$ does not exist.

But let me prove this directly anyway, since it’s so easy. Take a model of ETCS. If $\beth_\omega$ does not exist in it, we’re done. If it does, call a set “small” if it is $\lt \beth_\omega$. Since $\beth_\omega$ is a strong limit, the small sets are a model of ETCS in which $\beth_\omega$ does not exist. That’s it!

The axiom “all beths exist” is quite useful. Here’s an example. Suppose we start with a vector space $V$, and we want to form the colimit in $\mathbf{Vect}$ of the sequence

$V \to V^{\ast\ast} \to V^{\ast\ast\ast\ast} \to \cdots,$

where each map is the canonical embedding of a space into its double dual. What do we need to add to ETCS in order to be sure that this colimit exists (or, indeed, that this diagram is even mentionable)?

A little thought reveals that we’re OK as long as for any set $X$, the sets

$X, 2^X, 2^{2^X}, \ldots$

have a supremum. (This sufficient condition is necessary too, as you can see by thinking about vector spaces over $\mathbb{F}_2$.) Now assume that all beths exist. We can find some beth at least as big as $X$: for example, if we take a well order $W$ with underlying set $X$, then $\beth_W \geq U(W) \cong X$. And then $\beth_{W + \omega}$ is a supremum for this sequence of sets. (I’ll explain the meaning of $+$ in a moment; it’s what’s usually called “ordinal sum”.)

So, “all beths exist” guarantees the existence of such colimits.

The existence of all beths is a stronger condition than the existence of uncountable strong limits — stronger, even, than the existence of unboundedly many strong limits. First let’s see why one implies the other:

All beths exist $\implies$ unboundedly many strong limits.

Suppose we have a model of ETCS in which all beths exist. Take any set $X$. Our task is to find some strong limit $\geq X$, and we might as well assume that $X$ is infinite. Now, there’s some initial well order $W$ with underlying set $X$, and then

$X \cong U(W) \leq \beth_W.$

So $X \leq \beth_W$. Since $W$ is an initial well order (i.e. $\preceq$-least of its cardinality) and infinite, it can’t be a successor. So $W$ is a limit, which implies that $\beth_W$ is a strong limit.

(Again, this might seem familiar, because I gave the same argument last time for alephs and weak limits rather than beths and strong limits.)

“All beths exist” is strictly stronger than “there are unboundedly many strong limits”. That is:

It is consistent with ETCS + (there are unboundedly many strong limits) that not all beths exist.

It seems to be a feature of categorical set theory that ordinal arithmetic plays a less prominent role than in more traditional treatments. Nevertheless, we’ll need a little bit to prove this result.

The basic definitions are these. Given ordered sets $V$ and $W$, we can form:

• Their sum $V + W$. This is the disjoint union of $V$ and $W$, with the original orderings on each of the parts $V$ and $W$, and with $v \lt w$ whenever $v \in V$ and $w \in W$.

• Their reverse lexicographic product $V \cdot W$. Its underlying set is the cartesian product $V \times W$, and we define $(v, w) \lt (v', w')$ if either $w \lt w'$ or ($w = w'$ and $v \lt v'$).

If $V$ and $W$ are well-ordered then so are $V + W$ and $V \cdot W$. We’ll be talking about $\omega^2 = \omega \cdot \omega$ and $\omega \cdot n = \omega + \cdots + \omega$ for natural numbers $n$.

Now take a model of ETCS with unboundedly many strong limits. We want to build a model with unboundedly many strong limits in which not all beths exist.

If $\beth_{\omega^2}$ does not exist in this model, we’re done.

Now assuming that $\beth_{\omega^2}$ does exist in our model, call a set “small” if it’s $\lt \beth_{\omega^2}$. Since the well-ordered set $\omega^2$ is a limit, the set $\beth_{\omega^2}$ is a strong limit, so the small sets are a model of ETCS in which not all beths exist. We have

$\omega^2 = \sup_{n \in \mathbb{N}} \omega \cdot n,$

which implies that

$\beth_{\omega^2} = \sup_{n \in \mathbb{N}} \beth_{\omega \cdot n}.$

Hence every small set is $\leq \beth_{\omega \cdot n}$ for some natural number $n$. And since the well-ordered set $\omega \cdot n$ is a limit, the set $\beth_{\omega \cdot n}$ is a strong limit, giving us the conclusion we wanted: every small set is $\leq$ some small set that’s a strong limit.

Last time, I promised to give you the proof of the analogous statement for alephs and weak limits:

It is consistent with ETCS + (there are unboundedly many weak limits) that not all alephs exist.

But now that I think about it harder, I’m not sure I can fulfil that promise. So let me show you the argument I had in mind and ask for your help in filling the gap it contains.

It goes like this. Take a model of ETCS with unboundedly many weak limits. I think we can assume that our model satisfies the generalized continuum hypothesis. In that case, weak and strong limits are the same, and alephs and beths are the same, so the statement to be proved follows from the one I just did prove. And that’s it.

The question is whether it’s consistent with ETCS and the existence of unboundedly many weak limits that the generalized continuum hypothesis (GCH) holds. Certainly GCH is consistent with ETCS alone. I imagine that if I went through the proof of this theorem, I’d be able to adapt it so that the axiom “there are unboundedly many weak limits” came along for the ride with the rest of the ETCS axioms. But I don’t know this. Do you?

#### Next time

We’ve repeatedly used the inequality $U(W) \leq \beth_W$ for well-ordered sets $W$. At first, it may seem implausible that equality could ever hold, given how vastly bigger $\beth_W$ is than $W$ for small values of $W$. But it can! Or at least, requiring the existence of some $W$ such that $U(W) \cong \beth_W$ is a sensible “large set” axiom (and already implied by ZFC). Such $W$s are called beth fixed points, and they’re our subject for next time.

Posted at June 24, 2021 3:45 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3325

### Re: Large Sets 6

I’ve always assumed that the empty well-ordered set “should” be considered a limit, and that it’s only excluded sometimes for conventional reasons. In particular, it is a “limit” in the obvious sense that it can be written as the supremum of a set of well-ordered sets strictly smaller than itself (namely the empty such set).

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

### Re: Large Sets 6

Yes, that seems like a decent reason. There’s a counterargument that if we say $0$ isn’t a limit then we have the nice result that in the order topology on the ordinals, the limit points are exactly the limit ordinals. But I don’t find that compelling.

I’d wondered whether there was a too simple to be simple reason for excluding $0$ from the class of limit points. But I can’t see one.

My guess is that the convention of excluding $0$ has arisen for the practical reason that in transfinite inductions, one often wants to split into three cases (empty, successor, nonempty limit) rather than two (empty-or-limit, successor).

Posted by: Tom Leinster on July 2, 2021 4:06 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:53 AM
Read the post Large Sets 12
Weblog: The n-Category Café
Excerpt: Replacement is a natural supplement to ETCS.
Tracked: July 18, 2021 8:16 PM
Read the post Borel Determinacy Does Not Require Replacement
Weblog: The n-Category Café
Excerpt: Despite what they say.
Tracked: July 24, 2021 1:42 AM

### Re: Large Sets 6

Looking back at this post six weeks later, I see I missed out something quite important.

I mentioned in Part 5 that every infinite set is an aleph. But what I didn’t address here is the question of whether infinite set is a beth. The answer is yes if and only if the generalized continuum hypothesis holds:

$GCH \ \iff\ \text{every infinite set is a beth}.$

The $\implies$ direction is pretty much immediate: if GCH holds then beths are the same as alephs, and since every infinite set is an aleph, it follows that every infinite set is a beth.

Before I prove the converse, let’s quickly observe that if the actual (not generalized) continuum hypothesis fails then there’s some set $X$ satisfying $\mathbb{N} \lt X \lt 2^{\mathbb{N}}$, i.e. $\beth_0 \lt X \lt \beth_1$, and clearly such an $X$ can’t be a beth.

For the proof of the converse, I’ll assume that every infinite set is a beth and prove GCH in the following form:

$Y \lt X \implies 2^Y \leq X$

for infinite sets $X$ and $Y$. Indeed, suppose that $Y \lt X$. We have $Y = \beth_V$ and $X = \beth_W$ for some well-ordered sets $V$ and $W$, and since $Y \lt X$, it follows that $V \prec W$. But then $V^+ \preceq W$, so $\beth_{V^+} \leq \beth_W$, i.e. $2^Y \leq X$.

Posted by: Tom Leinster on August 6, 2021 3:09 PM | Permalink | Reply to this

### Re: Large Sets 6

It seems like there’s no reason to do case analysis on whether $\beth_\omega$ exists in the given model. We can instead say that a set is “small” if it smaller than all cardinals which are $\beth_\omega$. In general, if we wanted to provide a model of “there are at most $n$ strong limit cardinals” for some $n$, we could just say that a set is “small” if it is smaller than all but at most $n$ strong limit cardinals. But this is a bit of a nit pick.

Second, can you provide a source for the relative consistency of GCH with ETCS? I’ve been trying to work out some sort of variant of the classic V = L style proof that works with only ETCS’s bounded separation and lack of replacement, but I haven’t had any luck so far. Obviously if we start from a strong metatheory like ZFC then we can outright prove the consistency of GHC + ETCS, but I’m interested in working from a weak metatheory.

Thanks for the posts. They have proved interesting so far.

Posted by: Mark Saving on September 26, 2021 5:04 AM | Permalink | Reply to this

### Re: Large Sets 6

Thanks for these comments. I was uncomfortable having to resort to that case-by-case argument, but at the time I didn’t see a nice way around it. And I have a feeling there’s another one of these posts where the same thing happens.

Regarding the consistency of GCH with ETCS, good question. When I wrote the post, I had it in mind that it was in Mac Lane and Moerdijk’s book (Chapter VI), but as far as I can see it’s not. The original paper that they’re drawing from is Tierney’s “Sheaf theory and the continuum hypothesis” (1972), but the consistency of GCH with ETCS doesn’t seem to be there either. In both places, what’s proved is the Cohen-like result that not-CH is consistent with ETCS.

I very much hope that someone proved GCH is consistent with ETCS! Now that you mention it, I can’t even point to a proof that non-generalized CH is consistent with ETCS.

It would probably have been done in the first half of the 1970s. People working on this kind of thing then were certainly well aware that ETCS is weaker than ZFC, so they would have understood that there’s something to be proved.

Does anyone else know?

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

### Re: Large Sets 6

I believe Mathias’s “The strength of Mac Lane set theory” contains a construction of Gödel’s $L$ in a material set theory that is equiconsistent with ETCS.

Posted by: Mike Shulman on September 29, 2021 4:23 AM | Permalink | Reply to this

### Re: Large Sets 6

Thanks, Mike. My heart sinks at the prospect of extracting this result from a 128-page paper written in a language that I do not speak well, but I’ll give it a try.

Posted by: Tom Leinster on October 2, 2021 1:33 PM | Permalink | Reply to this

### Re: Large Sets 6

I have figured out a way to make the $V = L$ construction go through.

Lemma 1: prove in some suitable categorical set theory (Shulman identified a constructively well-pointed $\Pi$ pretopos as all that’s needed) to prove that given any indexed collection of extensional, well-founded relations $\{E_i\}_{i \in I}$, there exists an extensional well-founded relation that contains all the $E_i$ (for a suitable definition of “contains”). This is known in his paper as an “extensional quotient” and is important in the next proof.

Start with an interpretation of ETCS. Then, use the classic extensional well-founded relations technique to get an interpretation of BZ + “Every set has a transitive closure” + “Every extensional, well-founded relation is equivalent to a transitive set”.

In this theory, we see that given any set $S$ of extensional, well-founded relations, there is a set of the corresponding transitive sets (here, “indexed collection of sets $\{A_i\}_{i \in I}$” means a map $A \to I$, etc). To see this, apply lemma 1 to get an extensional, well-founded relation containing all the relations in $S$. Then, get the corresponding transitive set, and take all subsets of this transitive set which correspond to elements of $S$.

From here, prove that $\{t \mid t$ is transitive, $|t| \leq \kappa\}$ exists for all $\kappa$. To do this, note that $\{(E, e) \mid E \subseteq \kappa$ and $e$ is an extensional well-founded relation$\}$ is a set of extensional, well-founded relations. Take the corresponding set of transitive sets. For any transitive set $t$ such that $|t| \leq \kappa$, we see that there must be some injection $i : t \to \kappa$, and we can make an extensional, well-founded relation on $\exists_i(t)$.

Now, we can make the construction of $L$ go through. Recall that $Def(K) = \{ \{k \in K \mid \phi^K(k, x_1, ..., x_n)\} \mid \phi$ an $n + 1$-ary predicate, $x_1, ..., x_n \in K\}$. Here, $\phi^K$ means $\phi$ with all quantifiers relativised to $K$.

Then $L$ is recursively defined by $L_\alpha = \bigcup_{\beta \lt \alpha} Def(L_\beta)$ for all $\beta \lt \alpha$ for all ordinals $\alpha$.

Note that $L_\alpha$ is always a transitive set. Moreover, note that for all finite $\alpha$, $L_\alpha$ is finite, and that for all infinite $\alpha$, $|L_\alpha| = |\alpha|$. This can be proved by induction on $\alpha$. Some care is needed with the axiom of choice, but this is not too much of an issue since it’s easy to define a well-ordering on $L_\alpha$.

Therefore, we see that $L_\alpha$ exists for all $\alpha$, because the recursion can be carried out to construct a function $\ell : s(\alpha) \to \{t \mid$ a transitive set$\mid |t| \leq |\omega + \alpha|\}$ where $\ell(\beta) = L_\beta$ for all $\beta \leq \alpha$.

From here, most of the axioms of BZ are easy to verify in $L$. The tricky one is powerset. Some technical theorems are required. But the key result is that $P(L_\kappa) \subseteq L_{\kappa^+}$ for all cardinals $\kappa$.

We can, of course, show that $L$ is a model of $V = L$. Therefore, we can conclude that for all infinite $\kappa$, we have $2^\kappa = |P(L_\kappa)| \leq |L_{\kappa^+}| = \kappa^+$, proving GCH.

Posted by: Mark Saving on October 5, 2021 4:05 AM | Permalink | Reply to this

### Re: Large Sets 6

Bravo, Mark!

Still, the situation won’t be truly settled until somewhere in the published literature, the theorem “GCH is consistent with ETCS” is stated and proved. Can it really the case that no one’s done it already?

Posted by: Tom Leinster on October 7, 2021 11:08 AM | Permalink | Reply to this

Post a New Comment