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


($\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.

  • 2
    $\begingroup$ 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. $\endgroup$ – Derek Elkins Apr 26 '16 at 22:00
  • 1
    $\begingroup$ 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.) $\endgroup$ – Kaa1el Apr 26 '16 at 22:06
  • 1
    $\begingroup$ 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$. $\endgroup$ – Andrés E. Caicedo Apr 27 '16 at 0:12
  • 2
    $\begingroup$ (Also: Stop the yelling.) $\endgroup$ – Andrés E. Caicedo Apr 27 '16 at 0:13
  • 2
    $\begingroup$ @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. $\endgroup$ – 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.

I dk whether there has been any progress on the open problem of whether it can be shown in ZF that a regular uncountable cardinal exists.

  • 2
    $\begingroup$ The question in your last paragraph was solved negatively by Moti Gitik in MR0576462 (81h:03096). All uncountable cardinals can be singular, Israel J. Math. 35 (1980), no. 1-2, 61–88. $\endgroup$ – Andrés E. Caicedo Apr 27 '16 at 3:14
  • 1
    $\begingroup$ The precise consistency strength of $\mathsf{ZF}$+``all uncountable cardinals are singular'' is still open, though. $\endgroup$ – Andrés E. Caicedo Apr 27 '16 at 3:15
  • $\begingroup$ @Andres Caicedo. Thank you for the reference. $\endgroup$ – DanielWainfleet Apr 27 '16 at 3:24
  • $\begingroup$ 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? $\endgroup$ – Kaa1el Apr 27 '16 at 11:53
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 27 '16 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.