# Does the regularity of $\omega_{\alpha+1}$ need Axiom of Choice?

Many books indicate yes to this question. However, I found the only lemma they claim to use AC is the following statement:

If $\{A_i\}_{i\in I}$ is a family of sets, then $|\bigcup_{i\in I}A_i|\leq|I|\sup_{i\in I}|A_i|$.

But if we replace this statement by the following version, then this does not require AC anymore.

If $\{\beta_\alpha\}_{\alpha<\gamma}$ is a sequence of ordinals, then $|\sup_{\alpha<\gamma}\beta_\alpha|\leq|\gamma|\sup_{\alpha<\gamma}|\beta_\alpha|$.

Proof: We map $\delta$ to the least $\alpha$ such that $\delta<\beta_\alpha$ together with the image of $\delta$ under the map $f:\beta_\alpha\to|\beta_\alpha|\to\sup_{\alpha<\gamma}|\beta_\alpha|$, i.e., $\delta\mapsto(\alpha,f(\delta))$.

This statement is used to prove:

For infinite $\kappa$, $\mathrm{cf}(\kappa)$ is the least cardinal $\lambda$ such that $\kappa=\sum_{\beta<\lambda}\kappa_\beta$, where $\kappa_\beta<\kappa$.

Proof:

($\leq$) Let $\kappa=\sum_{\alpha<\lambda}\kappa_\alpha$, where $\kappa_\alpha<\kappa$. We may assume $\kappa_\alpha\geq 1$ for all $\alpha<\lambda$. Then either $\lambda$ or one of $\kappa_\alpha$ is infinite. So $\kappa=\lambda\sup_{\alpha<\lambda}\kappa_\alpha$. If $\kappa=\lambda$, then $\mathrm{cf}(\kappa)\leq\lambda$. If $\kappa=\sup_{\alpha<\lambda}\kappa_\alpha$, then we have a cofinal sequence, so $\mathrm{cf}(\kappa)\leq\lambda$ in this case as well.

($\geq$) Let $f:\mathrm{cf}(\kappa)\to\kappa$ be a cofinal sequence and write $\lambda=\mathrm{cf}(\kappa)$. We may assume $f$ is nonzero. Then we see $\kappa=|\kappa|=|\sup_{\alpha<\lambda}f(\alpha)|\leq\lambda\sup_{\alpha<\lambda}|f(\alpha)|\leq\kappa$. And since $\lambda\sup_{\alpha<\lambda}|f(\alpha)|=\sum_{\alpha<\lambda}|f(\alpha)|$, we got the equality $\kappa=\sum_{\alpha<\lambda}|f(\alpha)|$.

Then the proof goes:

If $\omega_{\alpha+1}$ were singular, then $\lambda=\mathrm{cf}(\omega_{\alpha+1})\leq\omega_\alpha$. Write $\omega_{\alpha+1}=\sum_{\beta<\lambda}\kappa_\beta$, where $\kappa_\beta\leq\omega_\alpha$. Hence, $\omega_{\alpha+1}=\sum_{\beta<\lambda}\kappa_\beta\leq\sum_{\omega_\alpha}\omega_\alpha=\omega_\alpha^2=\omega_\alpha$, contradiction.

Maybe I made a mistake somewhere, I don't know. Could anyone identify where is AC hiding in this proof? Thanks!

Disclaimer: all cardinals are well-orderable ordinals.

• My impression is if you want to convince people your question is not a duplicate, you reference the questions it might duplicate and explain how your question is different and the answers to the other questions fail to answer your question. This provides evidence that you've considered possible duplicate questions, and it helps answerers know what it is you are and are not looking for. – Derek Elkins Apr 26 '16 at 22:00
• The linked question is math.stackexchange.com/questions/1758211/… (given by the one who flagged duplicate) which is about the understanding the proof, NOT about the usage of axiom of choice. He also uses a different proof. However, there is another link given by the first answer to the linked question, but from what I read, AC is necessary in order to prove this fact, but that post is again NOT indicating where AC is used in the proof, but rather why it SHOULD be necessary (it is consistent with ZF that omega1 has countable cofinality.) – Kaa1el Apr 26 '16 at 22:06
• The statement you mentioned as not requiring choice if the $A_i$ are well-orderable actually uses choice even in that case. There are models where the inequality fails with $I=\omega$, each $A_i$ a countable subset of $\omega_1$, and $\bigcup_i A_i=\omega_1$. – Andrés E. Caicedo Apr 27 '16 at 0:12
• (Also: Stop the yelling.) – Andrés E. Caicedo Apr 27 '16 at 0:13
• @Kaa1el There is a rule against posting the question again. We even have a message template for that. The correct way is, as Asaf pointed out, to edit the original question to make clear why it's not a duplicate, then it will be reopened if the argument is convincing. If things don't work out, turn to Mathematics Meta. – Daniel Fischer Apr 29 '16 at 14:03

You have a hidden assumption in the proof of your first proposition. If $\beta_{x}\leq d<d'<\beta_{\alpha}$ whenever $x<\alpha ,$ then in order that the map that sends $d$ to $(\alpha,f_{\alpha}(d))$ be 1-to-1, you need each$f_{\alpha}:\beta_{\alpha}\to |\beta_{\alpha}|$ to be 1-to-1. Now for each $\alpha$, such $f_{\alpha}$ exists but it is generally not unique, so we cannot apply the Replacement Axiom to assert the existence of the sequence $(f_{\alpha})_{\alpha < \beta}.$ This is where AC is hiding.
Even when trying to prove in ZF that $\omega_1$ is regular, we hit this difficulty when we try to show in ZF that a countable union of countable ordinals is countable.
• The precise consistency strength of $\mathsf{ZF}$+all uncountable cardinals are singular'' is still open, though. – Andrés E. Caicedo Apr 27 '16 at 3:15
• Thanks for your answer. So does that mean the characterization of cf($\kappa$) as a sum requires AC as well? Can AC be avoided somehow in the proof? – Kaa1el Apr 27 '16 at 11:53
• If I understand you, we can, in ZF, define $cf(k)$ as the least $m\in ON$ such that $k=\sum_{a\in m}f(a)$ for some $f:m\to k.$ See the above comments. Proving in ZF that $\omega_1$ is regular would prove that a measurable cardinal doen't exist, which I think wold be quite a shock, and might win you a Fields medal. – DanielWainfleet Apr 27 '16 at 21:54