Ytukyg

One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $aleph_2$. My solution shows that it does not have cardinality $aleph_n$, where $n$ is any non-zero ordinal (not necessarily finite). I have a sneaking suspicion that my solution is actually invalid, but I can't find any reference which invalidates my conclusion.

I have read that it is provable in ZF that there are no cardinals $kappa$ such that $aleph_0 < kappa < aleph_1$, but I believe the conclusion of my proof does not preclude the possibility that the cardinality is incomparable to $aleph_1$ or some such.

I think the weakest point in my solution is where I claim that the supremum of a countable set of countable ordinals is again countable. This is true, of course, but it sounds uncomfortably close to the claim "a countable union of countable sets is countable", which is well-known to be unprovable in ZF. Can anybody confirm that the ordinal version is provable in ZF though? If not, I think I can weaken the claim to "the supremum of any set of countable ordinals is at most $omega_1$", and this establishes the weaker result that the cardinality of a countable union of countable sets is not $aleph_n$ for any ordinal $n ge 2$.

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_iotalekappa^+$. Use this to define a surjection $f$ from $kappatimes o$ onto $alpha$, from which it follows that there is an injection from $alpha$ into $kappatimes o$, and therefore a injection from $alpha$ into $kappa^+$:

Given $(iota,beta)in kappatimes 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 $gammain 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.)