Asaf Karagila
I don't have much choice...

Cofinality and the axiom of choice

There are 5 comments on this post.

What is cofinality of a[n infinite] cardinal? If we think about the cardinals as ordinals, as we should in the case the axiom of choice holds, then the cofinality of a cardinal is just the smallest cardinality of an unbounded set. It can be thought of as the least ordinal from which there is an unbounded function into our cardinal. Or it could be thought as the smallest cardinality of a partition whose parts are all "small".

Not assuming the axiom of choice the definition of cofinality remains the same, if we restrict ourselves to ordinals and \(\aleph\) numbers. But why should we? There is a rich world out there, new colors that were not on the choice-y rainbow from before. So anything which is inherently based on the ordering properties of the ordinals should not be considered as the definition of an ordinal. So first let's recall the two ways we can order cardinals without choice.

Definition. If \(A\) and \(B\) are sets, we write \(|A|\leq|B|\) if there is an injection from \(A\) to \(B\), and \(|A|\lt|B|\) if there is an injection, but there are no bijections; we write \(|A|\leq^*|B|\) if there is a surjection from \(B\) onto \(A\), or if \(A\) is empty, and equivalently \(|A|\lt^*|B|\) if there is a surjection (or \(A\) empty) and there is no surjection from \(A\) onto \(B\).

Some observations in \(\ZF\):

  1. If \(|A|\leq|B|\), then \(|A|\leq^*|B|\).
  2. \(\leq\) is antisymmetric, this is the Cantor-Bernstein theorem.
  3. \(\leq^*\) is not necessary antisymmetric. It can be shown, for example, that if \(\leq^*\) is antisymmetric then there are no Dedekind-finite cardinals, and that there is a non-measurable set.
Recall that without the axiom of choice neither of these orders need be well-founded. So it might be that there are sets of cardinals without a minimal element in them.

Definition. Given a set \(A\), we say that \(|I|\) is a cofinality of \(A\) if \(|I|\) is a \(\leq\)-minimal with respect to the property "There is a map from \(A\) onto \(I\) with every fiber having size \(\lt|A|\)." We similarly define \(*\)-cofinality using \(\leq^*\)-minimality. We say that \(|A|\) is regular (respectively \(*\)-regular) if it is its unique cofinality (\(*\)-cofinality).

Some consistent examples in \(\ZF\):

  1. If \(A\) is Dedekind-finite, then \(A\) has cofinality \(2\). Every partition of \(A\) into more than one part will have both parts strictly smaller than \(A\).
  2. If \(\RR\) is the countable union of countable sets then \(\omega\) is a cofinality of \(\RR\), and in that case König's theorem fails since the cofinality of \(2^\omega\) is in fact \(\omega\).
  3. It is consistent that every non well-orderable set has cofinality \(2\). This was shown by Monro ("Decomposable Cardinals", Fund. Math. vol. 80 (1973), no. 2, 101–104.), more specifically the real numbers can have cofinality \(2\).
Theorem. Cofinality can be singular, in particular the cofinality of a cofinality need not be a cofinality itself.

Proof. Recall the Solovay model where we start with \(L\) (for good measure) and an inaccessible cardinal \(\kappa\), then consider the collapse of all the ordinals below \(\kappa\) to be countable, and we define an intermediate model where every set of reals is Lebesgue measurable, has the Perfect Set Property, the Baire Property, \(\DC\) holds and \(\omega_1\) is regular.

Less known, but far more surprising is the generalization given by Truss ("Models of set theory containing many perfect sets", Ann. Math. Logic 7 (1974), 197-219.). There we work with a general limit cardinal (over \(L\) for good measure), and it can be shown that the resulting model will always satisfy the following:

  1. Every set of reals has the perfect set property. In particular every uncountable set of reals has size continuum.
  2. The countable union of countable sets of reals is again countable.
  3. \(\omega_1\) is singular if and only if \(\kappa\) was not inaccessible in \(L\).
You may recall the famous Feferman-Levy model in which the real numbers are a countable union of countable sets. Trivially (2) fails there, and recently Arnie Miller showed that (1) fails in that model as well. So what is this construction of the Truss model?

Let \(\PP\) be the finite support product of \(\Col(\omega,\alpha)\) for all \(\alpha\lt\kappa\). Namely, we collapse all the ordinals below \(\kappa\) and not just the cardinals below \(\kappa\) (which is \(\aleph_\omega\) in the traditional Feferman-Levy construction). So a condition \(p\) in \(\PP\) is a finite set of tuples of the form \(\tup{\alpha,n,\beta}\) where \(\alpha\lt\kappa\), \(n\lt\omega\) and \(\beta\lt\alpha\), and moreover if \(\tup{\alpha,n,\beta}\) and \(\tup{\alpha,n,\gamma}\) both appear in \(p\), then \(\beta=\gamma\).

The automorphism group \(\cG\) of \(\PP\) is fairly simple. It contains all the automorphisms which fix the \(\alpha\) coordinate, but can move \(n\) and \(\beta\) freely within the bounds of the definition of \(\PP\). Namely we can permute each \(\Col(\omega,\alpha)\) independently. Although since the conditions are finite, it is enough to consider automorphisms which act only on finitely many \(\alpha\)'s at a time.

Finally, we consider the filter of subgroups generated by \(\fix(\alpha)=\{\pi\in\cG\mid\forall\beta\lt\alpha:\pi\restriction\Col(\omega,\beta)=\id\}\). Namely, we look at groups which fix pointwise a proper initial segment of the forcing.

Lemma. For every \(\alpha\lt\kappa\), let \(\dot R_\alpha\) be the name of all the nice names of reals (names that only refer to \(\check n\) sort of names for integers), all of which are fixed by \(\fix(\alpha)\). Then \(\dot R_\alpha\) is fixed pointwise by every automorphism, and the name of the sequence \(\{\tup{\check\alpha,\dot R_\alpha}^\bullet\mid\alpha\lt\kappa\}^\bullet\) is fixed pointwise by every automorphism also. \(\square\)

It follows, if so, that the sequence of \(R_\alpha\)'s as interpreted in the symmetric model is a sequence of sets of reals; and that it has length \(\omega_1\) in the symmetric model. Moreover it is not hard to show that if \(\dot r\in\dot R_\alpha\), then essentially \(\dot r\) is a name defined by the collapse up to \(\alpha\). Therefore by the time we collapsed a sufficiently large ordinal, \(R_\alpha\) became a countable set.

Moreover, every real number in the symmetric model must appear at some \(R_\alpha\). So we have that the real numbers are now an \(\aleph_1\)-union of countable sets. If we didn't start with an inaccessible, this means that \(\omega_1\) is a contender for being a cofinality of \(\frak c\). For this we need to show its minimality. But now this follows by condition (2) of the reals in our model.

If we partition the reals into countably many parts, then it is impossible for all of them to be countable, since the countable union of countable sets of reals is again countable, and \(\aleph_0\lt\frak c\). So one part at least must be uncountable, and all uncountable sets of reals must have size continuum by (1). Therefore \(\aleph_0\) is not a cofinality of \(\frak c\). And trivially (1) also gives us that no finite integer can be a cofinality of \(\frak c\) as well.

In conclusion we have that \(\frak c\) itself is a cofinality of \(\frak c\), since it is minimal with respect to this ordering and we can always partition into singletons. But also \(\omega_1\) is a cofinality of \(\frak c\) as shown above, despite being singular if we started with a singular \(\kappa\). Moreover, since \(\omega_1\leq^*\frak c\) in \(\ZF\), it follows that \(\frak c\) is not a \(*\)-cofinality of itself, and therefore \(\omega_1\) is the \(*\)-cofinality of \(\frak c\) in Solovay/Truss models. \(\square\)

Conclusions. Cofinality of non-ordinals is weird without the axiom of choice. But it is not without apparent uses. If we want to add a function from a set \(A\) to a set \(B\), and we know that both have "reasonable" cofinalities we can talk about conditions whose cardinalities are small, and the forcing has more chance to satisfy some closure, distributivity and perhaps even chain conditions. So despite being a weird quirk, it is not something that should be dismissed easily.

I will try to write this, with more details and perhaps more interesting things to say about cofinality of arbitrary cardinals in \(\ZF\), into a nice note and post it here and/or arXiv over the next couple of weeks, so stay tuned for more!

What do you think? Is the definition of cofinality reasonable? Suitable? How would you change it, if at all?

(This entire shebang started from a discussion with David Roberts, which leaked into a discussion with Joel Hamkins in these comments, which turned into a discussion with Yair Hayut earlier today at the university. I'd like to thank all of them for poking the right spots of my brain for this to leak out.)

There are 5 comments on this post.

By Joel David Hamkins
(Nov 30 2015, 15:57)

Thanks for this post, Asaf! Do you have a set with two distinct cofinalities? Also, is your definition of \(<^*\) correct? (You said \(A<^*B\) if \(B\) surjects onto \(A\) but they are not bijective.) I would have expected you to say that \(A<^*B\) if \(A\leq^*B\) but not conversely. After all, if two sets surject onto each other, but they are not bijective, then we would have \(A<^*B<^*A\) according to your current definition, but I think we want it to be transitive.

By Asaf Karagila
(Nov 30 2015, 16:11 In reply to Joel David Hamkins)

You're welcome, Joel. It was fun thinking about it and writing it up. Let me first point out that if you are interesting in \(\leq\)-cofinalities, then \(\RR\) is an example in the Solovay/Truss model of a set with two cofinalities, both \(\frak c\) and \(\omega_1\). If you're interested in \(*\)-cofinalities, I'm sure something can be arranged, but I have nothing off hand. It still remains to see what happens under AD, by the way.

Regarding \(<^*\), you are probably right. And I'll fix that. Since I only had in mind the case of \(\RR\) and \(\omega_1\), this definition was less important since in the case that \(\RR\) cannot be well-ordered it is always the case that \(\omega_1<^*\RR\) in either definition.


By David Roberts
(Dec 03 2015, 13:32)

Thanks for putting in all the details, Asaf!

With all the discussion last week, and comments at MO, I'd lost sight of what I wanted my definition of cofinality to be! Namely this: the cofinality of a set \(X\) is the collection of all sets \(I\) (or set of such, when that makes sense) such that all surjections \(Y\to I\) with fibres smaller than \(X\) have \(Y\) smaller than \(X\). Clearly this comes in two flavours (and in fact three, once excluded middle goes: 'smaller' then means 'subquotient'). In the case that AC holds, then I believe this in fact gives the usual definition of cofinality, and we are coming at it from 'below'. In the discussion above, and sparked by my MO question, one tries to approach the cofinality from above, but there is an issue if the order relation is not well-founded. In private discussion with Asaf I mentioned that one should take all possible sets that could be said to be greater than a cofinality, if one existed, or even if it didn't. But this is a notion "open at the top"; it's hard to see that this just gives a set of sets.

The motivation for defining things this way, from below, is that cofinality is measuring what sort of disjoint unions the category of all sets smaller than \(X\) has. A set is regular if it has disjoint unions indexed by any set smaller than it, which gives a good fragment of set theory when combined with other properties of sets - in fact everything bar powerset, depending on assumptions.

The application to the usual inequality of König is that the category of sets smaller than \(PX\) should have all disjoint unions indexed by \(X\). Note that this doesn't even say anything about cofinality, or about all possible index sets for the disjoint union. And it was about this concept I should have asked on MO. Maybe I'll ask a separate question, or else edit it in, if either of you think it worthwhile.

By Asaf Karagila
(Dec 04 2015, 14:26 In reply to David Roberts)

Hi David,

It is an interesting take on cofinality, namely as the collection of all sets that whenever you map \(X\) onto them, at least one fiber is equipotent with \(X\) (which seems to me as equivalent to what you're saying). This is not quite the same as usually when assuming choice, since it gives you a proper class (even without choice). You can instead talk about cardinalities of such sets, or try and bound them in rank (in a choiceless context too), but in the context of AC you'd only get the cardinals below the cofinality, not all the ordinals. In the choiceless context I imagine it should be possible to arrange a set without a "set cofinality" as you suggest it to be.

The way I see it, cofinality should be a cardinal function (or a cardinal-set function). So it should return a set of cardinals (or a single cardinal if that set is a singleton). But in any possible definition for cofinality which has any "moral and philosophical justification" (and there are many, as we see), when the axiom of choice is out, things become extremely cumbersome. So I think that the right way to figuring this out should be to ask what sort of uses one aims to get from the definition of cofinality. If it's distributivity of Cohen-like forcings, to ensure that you're not adding small sets or causing too much damage, then the definition of cofinality should be one that allows you to do that in a nontrivial way (because proving that only for regular cardinals it's possible, but only ordinals can be regular cardinals, that would be a terrible theorem (or a wonderful one (look a lisp joke))).

I think that you and I ultimately want the same goal, but through completely different paths (and I'm not just talking about algebraic set theory vs. material set theory). And that makes life interesting.

By David Roberts
(Dec 04 2015, 14:57 In reply to Asaf Karagila)

Yes, I should be a little more careful as to what I mean by 'all sets such that...'. You are spot on about getting all ordinals vs just the cardinals. I guess I was thinking of just the cardinals, but to get the usual cofinality as the sup of the collection of sets that I described is a little bit more subtle. Would one want to take, in the presence of AC, something like a sup or a successor cardinality? I guess it depends on whether the collection I described has a top element or not.

My aim really is something like I described, namely being able to say how many colimits the category of sets below a certain size has, since the notion of being closed under an operation is to my mind quite important. But knowing how forcing behaves is of course vital. I haven't yet delved enough into different sorts of forcings in a constructive setting that require knowing about cofinalities (terrible, I know!), but my guess is that it's the closure property that one needs.

PS did you see my comment to you at MO? I think you have an answer in your example 3. in ZF above. Personally, I think the proof is using the choice function, rather than the actual well-ordering; this is only really important when in the absence of excluded middle there are different notions of well-ordering, and the existence of choice functions is actually stronger than the constructively correct notion of well-order.

Want to comment? Send me an email!