Large Sets 8
Posted by Tom Leinster
Previously: Part 7. Next: Part 9
If you’ve been wanting to follow this series but haven’t had time to keep up, now’s a good moment to hop back on board — I won’t assume much of what’s gone before.
Back in the mists of time, when I took a first undergraduate course on axiomatic set theory, I was exhilarated by the extraordinary world of infinite sets I saw opening up before me. In that world, addition is the same as multiplication! Which is the same as maximum! That is,
for all infinite and . It seemed unthinkably exotic.
I then heard this part of cardinal arithmetic called “trivial” for exactly the reasons just stated. Although that description is technically correct, it poured a bucket of cold water over my enthusiasm in a way that only mathematicians can.
So with apologies to my past self, I give you the informal title of this post: the nontrivial part of cardinal arithmetic.
Once we’ve seen that binary addition and multiplication are “trivial”, what’s left to do in cardinal arithmetic? Well, there’s addition and multiplication of infinitely many sets, and there’s exponentiation. Some of the theory of those operations is trivial too, in the sense of following immediately from the isomorphisms
for infinite and . Let’s get that trivial stuff out of the way first.
Addition, even infinitary addition, is more or less the same as supremum. An easy little argument shows that for any family of nonempty sets,
— unless, of course, it’s a finite family of finite sets. (The sum of finitely many natural numbers is not the same as its sup!)
Exponentiation is a special case of infinitary multiplication: . Still, it’s an important enough case that it’s well worth thinking about separately.
In many cases, exponentiation is trivial too. It’s trivial when the expression
is top-heavy — when is bigger than . It’s even trivial when is just slightly smaller than . Indeed,
assuming that and are infinite. The proof is a pushover:
For example, for all infinite sets .
There’s another case where exponentiation is trivial: when the base is the power set of something. Another one-line proof shows that if is a power set then
Here I’ve assumed again that and are infinite. If or is finite then exponentiation is trivial too.
So the only occasions when is not trivial to compute are when is not a power set and — the expression is “bottom-heavy”. It’s certainly the case that
But even assuming the generalized continuum hypothesis, this still leaves two options for : is it or ?
Now we’re moving across the boundary into what I’m calling the “nontrivial” part of cardinal arithmetic. (Of course, any professional would regard everything I’m saying here as trivial.) And it’s time to talk about the wonderful König’s theorem.
König’s theorem states that for any families of sets and whatsoever,
Let’s spend a while contemplating this result, before we start to think about the proof. Some observations:
There are many variant statements that can be obtained by taking König’s theorem and replacing one or both signs by , or by changing the sum to a product, or vice versa. All of those variants are either trivially true or false. (For example, changing both s to s gives a false statement.) Among these variants, König’s theorem is unique in being both nontrivial and true.
If we assume the generalized continuum hypothesis then König’s theorem does become trivial, at least when and are infinite. For then for every , and taking the product of these inequalities over all gives , hence the result.
When every is empty, König states that a product of nonempty sets is nonempty. This is equivalent to the axiom of choice (in the presence of the other ETCS axioms). So, we’re going to have to use the axiom of choice in the proof.
When and for all , König’s theorem becomes Cantor’s theorem: for all sets . So, we can expect the proof to be a generalization of the diagonal argument.
As for the proof, I won’t spoil it! I promise you that if you haven’t seen it before and you figure it out for yourself, it will brighten your day. It’s the proof of strict inequality that’s the really nice part.
When I first learned König’s theorem, I got a bit overexcited. I thought that such a general statement would be sure to have a wealth of applications. But as far as I know, there’s basically only one, and it’s this:
Let and be infinite sets. Suppose that can be expressed as a coproduct of sets that are all . Then .
Indeed, if with for each , then König’s theorem with for all gives the result.
For example, suppose we have a model of ETCS in which exists. Then
so
The right-hand side here is a very bottom-heavy exponential: is vastly bigger than .
At this point I want to talk about some bad intuition that I carried around with me for many years. I’ll explain it using the example of two particular sets, and , but other examples would work too.
, and my mental picture is that is bigger than and therefore “absorbs” it: adjoining tiny little to great big doesn’t make it any bigger. That intuitive idea is fine. (It’s crude, because even if and have the same cardinality. But that doesn’t make it wrong.)
, and my mental picture for this is similar: since is bigger than , taking copies of it doesn’t make it any bigger. That intuitive idea is fine too.
, and my mental picture for this used to be similar: since is bigger than , taking mere sequences of reals doesn’t give you a larger set than taking reals themselves. This intuition is completely wrong!
It’s wrong because there are sets much bigger than such that . Or at least, such sets exist as long as we add to ETCS a very mild extra axiom: the existence of an uncountable weak limit. Then exists, and as we just saw,
That’s why it’s nonsense to think that because is bigger than, or “absorbs”, .
End of digression.
For results like the “” one, it’s useful to think in terms of cofinality. By definition, the cofinality of an infinite set is the smallest set with the following property:
there is some family of sets such that and for all .
The word “cofinality” comes from an equivalent order-theoretic formulation which I won’t talk about.
Certainly the set has the stated property, since . So is well defined and . Some examples:
What’s the cofinality of ? Since a finite coproduct of finite sets is finite, any set with the property above must be infinite. So is infinite. But , so .
How about , the smallest set ? If is a family with and , then and . It follows that So cannot be expressed as a coproduct of sets that are all . That is, .
Generally, the same argument shows that if is a successor (that is, there’s some set such that is the smallest set ), then .
Assuming that exists, we have with for each . Hence .
As these examples show, many sets have the property that . Such sets are called regular. So
are all regular, as is any successor. An infinite set that is not regular is called singular. Thus, a set is singular if and only if it can be expressed as a coproduct of sets that are each .
Since the smallest example of a singular set is , and since it is consistent with ETCS that does not exist,
It is consistent with ETCS that every infinite set is regular.
(I’m only defining cofinality, and regular vs. singular, for infinite sets. I don’t know whether there’s a sensible way to set up the definitions for finite sets.)
Aside Regularity comes up quite naturally in category theory. For instance, take the result that finite limits commute with filtered colimits in . The definitions of finite limit and filtered colimit both refer (at least implicitly) to the concept of a set being finite, and finite means . One might seek to generalize the commutativity result by replacing by some larger set . But if one tries to do this, one quickly finds oneself needing the assumption that is regular. There’s a nice explanation of this point in Francis Borceux’s Handbook of Categorical Algebra, Volume 1, Section 6.4.
The cofinality of a set is always regular:
for every infinite set . (I won’t give the proof.) So is an operation converting arbitrary sets into regular sets.
This is another moment at which a category theorist might get overexcited. Perhaps feels like some kind of reflector of sets into regular sets, and perhaps the statements
suggest there’s a monad around. Not so fast! Cofinality is not order-preserving:
The subtle behaviour of the cf operation has driven a lot of research in set theory. For example, the extraordinarily prolific set theorist Saharon Shelah found new results in cardinal arithmetic using his PCF theory, where PCF stands for “potential (or possible) cofinalities”.
At the very least, the cf notation is highly convenient. Recall this result from earlier:
Let and be infinite sets. Suppose that can be expressed as a coproduct of sets that are all . Then .
We can rephrase it more compactly like this:
for all infinite .
This result, a corollary of König’s theorem, has an important corollary itself. Let be an infinite set and a set with at least two elements. Replacing by in the last result gives
and so
In other words, you can’t partition into smaller pieces.
In particular, this is true when , giving
for all infinite sets . Since for all , this is a sharpening of Cantor’s result that .
A nice application of the fact that is to show that is not the power set of anything in the world. (Allen Knutson mentioned this back in Part 4, and Todd Trimble gave a proof.) For if then
so is finite. But , so is finite, a contradiction.
Next time
Next time, we’ll climb another rung up the ladder of largeness, where we’ll find the inaccessible sets.
Re: Large Sets 8
Do you mean “if xor is finite”? (-: