Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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

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

“and so on”, with one set W\beth_W for each well-ordered set WW. 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 WW. Then W\beth_W is said to exist if V\beth_V exists for all well-ordered sets VWV \prec W and there is some infinite set XX such that 2 VX2^{\beth_V} \leq X for all VWV \prec W. In that case, W\beth_W is defined to be the smallest such set XX.

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 +V^+ for some other well-ordered set VV. (Recall that V +V^+ means VV 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 WW to be the empty well-ordered set 00 in the definition of beth tells us that 0\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 0\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 WW is a successor, say W=V +W = V^+. If V\beth_V exists then W\beth_W also exists, with W=2 V\beth_W = 2^{\beth_V}.

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

For example,

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

Here n\beth_n means n\beth_{\mathbf{n}}, where n\mathbf{n} is the unique nn-element well-ordered set. And ω\beth_\omega, if it exists, is the supremum of 0, 1,\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 W\beth_W and of what the set W\beth_W actually is. Here’s a non-inductive alternative.

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

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

the last member of which is W\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 VWV \preceq W. But that’s easily overcome: every well-ordered set VWV \preceq W is isomorphic to

w={vW:v<w} &#x21A1; w = \{ v \in W : v \lt w \}

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

( w) wW +. (\beth_{&#x21A1; w})_{w \in W^+}.

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

bundle showing family of beths up to beth-W

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

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

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

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

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

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

W W \aleph_W \leq \beth_W

for all well-ordered sets WW. More exactly, if W\beth_W exists then so does W\aleph_W and the inequality is true. If the generalized continuum hypothesis holds (X +=2 XX^+ = 2^X for all infinite sets XX) 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:

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

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

For all sets II, there exists a function p:EIp: E \to I into II such that for all distinct i,jIi, j \in I, either 2 p 1(i)p 1(j)2^{p^{-1}(i)} \leq p^{-1}(j) or 2 p 1(j)p 1(i)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 XY2^X \leq Y in place of X<YX \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 II to be the underlying set \mathbb{N} of ω\omega, since the fibres could all be finite. You have to use an uncountable II. 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

0=, 1=2 , 2=2 2 ,. \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

+2 +2 2 + \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:

bundle showing family of beths indexed by natural numbers

Got it? Let me say it in boring old words. Suppose that ω\beth_\omega exists. Then the set EE 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 SS. Then SS is certainly an upper bound of 0, 1,\beth_0, \beth_1, \ldots, so these sets have a least upper bound and it’s S\leq S. Hence ω\beth_\omega exists and is S\leq S. That proves that the supremum is the same as the sum, and it shows that the total space EE in the diagram is exactly ω\beth_\omega.

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

W=sup VW V= VW V. \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=ωW = \omega gets replaced by the general fact that U(W) WU(W) \leq \beth_W, where UU means underlying set. This follows from the chain of inequalities

U(W) W W, 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 WW is a limit then the set W\beth_W is a strong limit (recalling what this means: if X< WX \lt \beth_W then 2 X< W2^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 VV, and we want to form the colimit in Vect\mathbf{Vect} of the sequence

VV **V ****, 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 XX, the sets

X,2 X,2 2 X, 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 𝔽 2\mathbb{F}_2.) Now assume that all beths exist. We can find some beth at least as big as XX: for example, if we take a well order WW with underlying set XX, then WU(W)X\beth_W \geq U(W) \cong X. And then W+ω\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 XX. Our task is to find some strong limit X\geq X, and we might as well assume that XX is infinite. Now, there’s some initial well order WW with underlying set XX, and then

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

So X WX \leq \beth_W. Since WW is an initial well order (i.e. \preceq-least of its cardinality) and infinite, it can’t be a successor. So WW is a limit, which implies that W\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 VV and WW, we can form:

  • Their sum V+WV + W. This is the disjoint union of VV and WW, with the original orderings on each of the parts VV and WW, and with v<wv \lt w whenever vVv \in V and wWw \in W.

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

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

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 ω 2\beth_{\omega^2} does not exist in this model, we’re done.

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

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

which implies that

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

Hence every small set is ωn\leq \beth_{\omega \cdot n} for some natural number nn. And since the well-ordered set ωn\omega \cdot n is a limit, the set ωn\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) W U(W) \leq \beth_W for well-ordered sets WW. At first, it may seem implausible that equality could ever hold, given how vastly bigger W\beth_W is than WW for small values of WW. But it can! Or at least, requiring the existence of some WW such that U(W) W U(W) \cong \beth_W is a sensible “large set” axiom (and already implied by ZFC). Such WWs 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:

9 Comments & 3 Trackbacks

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 00 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 00 from the class of limit points. But I can’t see one.

My guess is that the convention of excluding 00 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:

GCHevery infinite set is a beth. 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 XX satisfying <X<2 \mathbb{N} \lt X \lt 2^{\mathbb{N}}, i.e. 0<X< 1\beth_0 \lt X \lt \beth_1, and clearly such an XX 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<X2 YX Y \lt X \implies 2^Y \leq X

for infinite sets XX and YY. Indeed, suppose that Y<XY \lt X. We have Y= VY = \beth_V and X= WX = \beth_W for some well-ordered sets VV and WW, and since Y<XY \lt X, it follows that VWV \prec W. But then V +WV^+ \preceq W, so V + W\beth_{V^+} \leq \beth_W, i.e. 2 YX2^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 nn strong limit cardinals” for some nn, we could just say that a set is “small” if it is smaller than all but at most nn 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 LL 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=LV = 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} iI\{E_i\}_{i \in I}, there exists an extensional well-founded relation that contains all the E iE_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 SS of extensional, well-founded relations, there is a set of the corresponding transitive sets (here, “indexed collection of sets {A i} iI\{A_i\}_{i \in I}” means a map AIA \to I, etc). To see this, apply lemma 1 to get an extensional, well-founded relation containing all the relations in SS. Then, get the corresponding transitive set, and take all subsets of this transitive set which correspond to elements of SS.

From here, prove that {tt\{t \mid t is transitive, |t|κ}|t| \leq \kappa\} exists for all κ\kappa. To do this, note that {(E,e)Eκ\{(E, e) \mid E \subseteq \kappa and ee 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 tt such that |t|κ|t| \leq \kappa, we see that there must be some injection i:tκi : t \to \kappa, and we can make an extensional, well-founded relation on i(t)\exists_i(t).

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

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

Note that L αL_\alpha is always a transitive set. Moreover, note that for all finite α\alpha, L αL_\alpha is finite, and that for all infinite α\alpha, |L α|=|α||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 αL_\alpha.

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

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

We can, of course, show that LL is a model of V=LV = L. Therefore, we can conclude that for all infinite κ\kappa, we have 2 κ=|P(L κ)||L κ +|=κ +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