The cardinality of a countable union of countable sets, without the axiom of choice

Solution 1:

The ordinal $\omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.

This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.

The result is that it is consistent with $\mathsf{ZF}$ that ${\mathbb R}$ is a countable union of countable sets. From this, it follows easily that $\omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.

The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $\omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.

In fact, things can be worse: Gitik showed that it is consistent with $\mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $\omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)

On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $\omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $\omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.

Let me add two comments about other things you say in your question: You write "I have read that it is provable in $\mathsf{ZF}$ that there are no cardinals $\kappa$ such that $\aleph_0<\kappa<\aleph_1$". This is true, but it is stronger than that: By definition $\aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $\aleph_0$ and $\aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $\kappa$ and its successor $\kappa^+$, by definition.

It is true, however, that a countable union of countable sets need not be comparable with $\aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.

Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $\omega_2$, we check more generally that if $\kappa$ is a (well-ordered) cardinal, then a union of $\kappa$ many sets, each of size at most $\kappa$, cannot have size $\kappa^{++}$: Let $S_0,S_1,\dots,S_\beta,\dots$, $\beta<\kappa$, be sets of ordinals, each of size at most $\kappa$. Let $S$ be their union and let $\alpha={\rm ot}(S)$, the order type of $S$. Similarly, let $o_\iota={\rm ot}(S_\iota)$ for each $\iota<\kappa$. Each $o_\iota$ is an ordinal below $\kappa^+$ and therefore $o=\sup_\iota o_\iota\le\kappa^+$. Use this to define a surjection $f$ from $\kappa\times o$ onto $\alpha$, from which it follows that there is an injection from $\alpha$ into $\kappa\times o$, and therefore a injection from $\alpha$ into $\kappa^+$:

Given $(\iota,\beta)\in \kappa\times o$, define $f(\iota,\beta)=0$ unless $\beta<o_\iota$ and, letting $\gamma$ be the $\beta$-th element in the increasing enumeration of $S_\iota$, we have that $\iota$ is least such that $\gamma\in S_\iota$. If this is the case, then set $f(\iota,\beta)=\delta$, where $\delta$ is defined so that $\gamma$ is the $\delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.

(It is perhaps clear, but let me remark that if $\omega_1$ can be written as the countable union of countable sets, then any $\alpha<\omega_2$ can be written this way as well, so $\omega_2$ cannot be replaced with any smaller bound.)