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.

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

Don’t worry about it

In a recent Math.SE question about the foundations of category theory without set theory, someone made a claim that $\ZF$ makes it hard to learn mathematics, because in $\ZF$ the questions “is $\RR\subseteq\pi$?” and “is $\RR\in\pi$?” can be phrased. They continued to argue that there are questions like whether or not hom-sets are disjoint or not, which are hard to explain to people who are “drunk on ZF’s kool-aid”.

So I raised a question in the comment, and got replies from two other people who kept repeating the age old silly arguments of what are the elements of $\RR\times\RR$ or what are these or that elements. And supposedly the correct pedagogical answer is “It does not matter what are the elements of $\RR\times\RR$.” With that I strongly agree, and when I taught my students about ordered pairs on the very first class of the semester, I made it very clear that there are other ways to define ordered pairs and that we only do that because we want to show that there is at least one way in which ordered pairs can be realized as sets; but ultimately we couldn’t care less about what way they encode ordered pairs into sets, as long it is a “legal” way.

And it seems to me that a lot of the flak set theory gets comes from the inability, or rather the unwillingness of people outside of set theory to study just the little bit more than they absolutely have to. Perhaps set theory wasn’t properly introduced to them in their undergrad, maybe too early and maybe too late (after they had heard bad things about it from their algebra teachers complaining about proper classes and the axiom of choice).

I don’t know why people don’t do that, and I am very happy to have had the opportunity to work with Azriel Levy in the past three years and see how so many of our students love the topic. And this is not because Israel is a friendly place towards set theory, this becomes increasingly less true. It’s because they have a teacher and a teaching assistant (who is teaching another complementary half-course in the exercises) which come from set theory and do not shy away from questions like “Can we define ordered pairs in a different way? What happens then?” and it’s because they have teachers which are truly enthusiastic about set theory.

Students are impressionable. If you have a good teacher and they tell you something, this will stick with you. And if that good teacher tells you that set theory is the root of all evil, then you will continue to think so until, if you’re lucky, you’ll learn otherwise. Or, if you have a good teacher that tells you in your sophomore year that the axiom of choice is a dormant research topic, but it has a lot of beautiful mathematics and a lot of interesting open questions left… well, you end up like me.

So what’s the whole issue here? Is $\pi\subseteq\RR$? That depends, you haven’t given me a definition for the sets $\pi$ and $\RR$. But once you will give me a definition, my answer is that it doesn’t matter, because we are interested in structures with a certain property, not with specific sets. And that given any other way to interpret the real numbers as sets can yield different answers to the question.

And I truly don’t understand why this bothers people. There are three paths from here to the nearest groceries store, and all take about the same time and effort to cross. It means that if you ask me to go to the groceries store you can ask me if I passed this or that place, and the answer will depend on which path I took. And thank goodness I am not afraid of questions like “is $\pi\subseteq\RR$?”, because then the choice of path to the store would have terrified me, and I would be forced to move to the building right next to it, which I am told is really shitty.

In short, if there’s one thing to take from this post is that the people who are terrified of the ability to make sense of the questions like “is $\pi\subseteq\RR$?” are the people who are too terrified to understand that even set theorists don’t care about these questions. And if you worry about them, and find that to be a good argument against $\ZF$, then don’t. There are reasonable arguments against $\ZF$, but this is not one of them.

How do you read a paper?

Some time ago I was talking to some people about how they read a paper. And I learned that I am somewhat significantly different from a lot of people. I spent some time thinking about it, and I arrived at some interesting conclusions.

So here is how I read a paper, and I’d like to ask you to think about how you read a paper, and why you read it this way.

If I wasn’t looking for that specific paper (or if I haven’t been directed to that paper somehow), I’m going to look at the title and authors. If at least one of them catches my eyes as interesting, I’ll proceed.

Next comes the abstract, which I might scan if it seems too long or too dense. And this is where we diverge from the norm.

After the abstract comes the acknowledgments, if there are any. I’m not necessarily looking for my name there. Heck, my contribution to mathematics so far is fairly insignificant to be mentioned in the acknowledgments of most paper I’m going to open. But if you know who the authors are acknowledging, you know more about the psyche of the work. You know where it happened, and you know who were the people that were consulted while the research and writing were in progress. That tells you a lot, because you don’t do mathematics in vacuum. In space no one can hear you prove.

Then I go back and read the introduction, and then I will decide whether or not I am going to read the rest, or just a part of the paper, or if I am going to scan the entire thing for interesting words in the theorems or definitions. When I do read, I won’t usually get into the proofs. I will, eventually, if I feel that I need to, or if I’ve come looking for a particular proof or trick, but generally I will look at the theorem and try to understand why they might be true.

That’s my process. I remember a lot of theorems, but very few proofs, which is not necessarily a bad thing, but not always a good thing (especially when you remember just 85% of the right formulation of the theorem!), but it all works out at the end. You can always go and read through the proof if you feel that you need to.

And it is interesting that a lot of people don’t pay a lot of attention to acknowledgments. Recently I read a preprint by someone I know, and I remarked that there are no acknowledgments. They replied by saying that it’s senseless to give acknowledgment to the referee now; but surely they had other acknowledgments to give (in fact, I know they have (not to me, if that matters)). And after that I noticed that it’s not uncommon for a preprint not to have any acknowledgments, at least in the initial version.

I find that odd. And I’m sure that up until this point, I was the only one (modulo finitely many exceptions perhaps).

So how about you? How do you read a paper, and more importantly, why do you read it that way? (And please put acknowledgments in your preprints!)