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 and repeatedly take power sets. They are
“and so on”, with one set for each well-ordered set . The symbol 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 . Then is said to exist if exists for all well-ordered sets and there is some infinite set such that for all . In that case, is defined to be the smallest such set .
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 for some other well-ordered set . (Recall that means 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 to be the empty well-ordered set in the definition of beth tells us that does exist, and that it’s the smallest infinite set — namely, . The sole reason why the word “infinite” is in the definition of beth is to make be equal to rather than . That’s just convention; I see no compelling reason to begin the beths at rather than .
Suppose that is a successor, say . If exists then also exists, with .
Suppose that is a limit. In order for to exist, it must certainly be the case that exists for all . That doesn’t guarantee that exists, but if it does, it’s the least upper bound of these sets :
For example,
Here means , where is the unique -element well-ordered set. And , if it exists, is the supremum of .
This inductive definition of the beths is slightly tricky, in that it’s simultaneously an inductive definition of the existence of and of what the set actually is. Here’s a non-inductive alternative.
The idea is that if exists then we should be able to directly characterize the family of sets
the last member of which is 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 . But that’s easily overcome: every well-ordered set is isomorphic to
for a unique . So strictly speaking, our family is
And in ETCS, families are expressed as maps into the indexing set, so the picture is this:
Formally, let be a well-ordered set. Then exists if and only if there exist a set and a function with the following property:
for all , the fibre is the least infinite set for all .
In that case, and are determined uniquely up to isomorphism, and is defined as the fibre over the greatest element of .
If all this seems rather familiar, it should! I gave a precisely analogous characterization of rather than last time, with in place of .
Generally, if we write to mean , then the difference between the alephs and the beths is the difference between and . Since if and only if , this is another way of expressing the thought that the alephs are to the beths as is to .
With this in mind, it’s easy to see that
for all well-ordered sets . More exactly, if exists then so does and the inequality is true. If the generalized continuum hypothesis holds ( for all infinite sets ) 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:
exists for every well-ordered set .
There’s an equivalent way of saying this that’s not inductive and doesn’t mention order either:
For all sets , there exists a function into such that for all distinct , either or .
Again, this is an analogue of something I already said for the alephs, but with the relation in place of .
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 exists. It’s not enough to take to be the underlying set of , since the fibres could all be finite. You have to use an uncountable . 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 . We saw that, if it exists, it’s the supremum of
But also, exists if and only if the coproduct
exists, and in that case, 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 exists. Then the set shown can be constructed as a subset of . And in fact, , since . Hence the coproduct exists and is . Conversely, suppose that the coproduct exists; call it . Then is certainly an upper bound of , so these sets have a least upper bound and it’s . Hence exists and is . That proves that the supremum is the same as the sum, and it shows that the total space in the diagram is exactly .
Everything I’ve just said about is equally true for every limit well-ordered set :
And the argument is the same too. The step “” in the case gets replaced by the general fact that , where means underlying set. This follows from the chain of inequalities
both of which I mentioned before.
In fact, we met 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, exists if and only if an uncountable strong limit exists, and in that case the smallest uncountable strong limit is .
Why is a strong limit? You should be able to persuade yourself that if a well-ordered set is a limit then the set is a strong limit (recalling what this means: if then ). In particular, the well-ordered set is a limit, so the set is a strong limit.
Since uncountable strong limits are not guaranteed to exist in a model of ETCS, and is an uncountable strong limit, we can deduce:
It is consistent with ETCS that does not exist.
But let me prove this directly anyway, since it’s so easy. Take a model of ETCS. If does not exist in it, we’re done. If it does, call a set “small” if it is . Since is a strong limit, the small sets are a model of ETCS in which 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 , and we want to form the colimit in of the sequence
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 , the sets
have a supremum. (This sufficient condition is necessary too, as you can see by thinking about vector spaces over .) Now assume that all beths exist. We can find some beth at least as big as : for example, if we take a well order with underlying set , then . And then 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 unboundedly many strong limits.
Suppose we have a model of ETCS in which all beths exist. Take any set . Our task is to find some strong limit , and we might as well assume that is infinite. Now, there’s some initial well order with underlying set , and then
So . Since is an initial well order (i.e. -least of its cardinality) and infinite, it can’t be a successor. So is a limit, which implies that 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 and , we can form:
Their sum . This is the disjoint union of and , with the original orderings on each of the parts and , and with whenever and .
Their reverse lexicographic product . Its underlying set is the cartesian product , and we define if either or ( and ).
If and are well-ordered then so are and . We’ll be talking about and for natural numbers .
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 does not exist in this model, we’re done.
Now assuming that does exist in our model, call a set “small” if it’s . Since the well-ordered set is a limit, the set is a strong limit, so the small sets are a model of ETCS in which not all beths exist. We have
which implies that
Hence every small set is for some natural number . And since the well-ordered set is a limit, the set is a strong limit, giving us the conclusion we wanted: every small set is 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 for well-ordered sets . At first, it may seem implausible that equality could ever hold, given how vastly bigger is than for small values of . But it can! Or at least, requiring the existence of some such that is a sensible “large set” axiom (and already implied by ZFC). Such s are called beth fixed points, and they’re our subject for next time.
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).