Cofinality and the axiom of choice

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.

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\).

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\).

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.)