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:

2 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

Post a New Comment