Cardinality of the union of a countable number of countable, well-ordered sets

Question

I know that the Axiom of Choice is required to show that the union of a countable number of countable sets is countable. However, what if the sets are well-ordered, i.e. we have a particular well-ordering for each set. Are we then able to show that the union is countable without the AoC?

Someone here mentions we can only show that it is at most $\aleph_1$ rather than $\aleph_0$, but I don't know whether this is correct or, if so, how one would show that.

Suppose that $S = \{A_n \,|\, n < \omega\}$ is our countable system of sets. Clearly then, since each $A_n$ is well-ordered, it is isomorphic to a unique ordinal number $\alpha_n$ where obviously $|\alpha_n| \leq \aleph_0$. Obviously if $\alpha_n = \omega$ then we can form a sequence whose range is $A_n$, but the problem is that it could be that $\alpha_n > \omega$ and still be the case that $\alpha_n$ is countable (for example the ordinal $\omega \cdot 2$ is still countable). In this case I don't see how we can generally choose a sequence whose range is $A_n$, which is what we need to do if the AoC is to be avoided.

I am actually trying to prove something more general: if $S = \{A_\beta\}_{\beta < \aleph_\gamma}$ is a transfinite sequence of well-ordered sets, and each $A_\beta$ in $S$ is at most $\aleph_\gamma$, then the union $\bigcup_{\beta < \aleph_\gamma} A_\beta$ is also at most $\aleph_\gamma$. However, I do not think there is any chance of proving this without choice if the case where $\gamma = 0$ (i.e. the case above where everything is countable) cannot even be proven without choice.

Answer 1

It is indeed possible that the countable union of countable, well-ordered sets can be uncountable. What's needed isn't a specific well-ordering, but rather a specific injection into $\omega$, for each of the sets involved.

To get a sense of what's going on here, notice that there is no canonical bijection between a infinite countable ordinal $\alpha$ and $\omega$. Even though we have a specific well-ordering of $\alpha$ in hand, we don't have a "certificate of countability"!

The snappiest way to describe this situation is probably:

It is consistent with ZF that $\omega_1$ (= the least uncountable ordinal) is singular (= is a union of countably many countable ordinals).

---

Now I've just said that it's consistent; can I prove it?

Well, not in this answer box, unfortunately. Consistency proofs in set theory are hard: even when we're just proving consistency with ZFC, we tend to need forcing, and for interesting violations of choice we need the further technique of symmetric submodels.

That said, here's a few words on the subject: a model of ZF + "$\omega_1$ is singular" was produced by Feferman and Levy very early on (I don't recall the exact date). The Feferman-Levy model is described in detail in a number of places, including Jech's book on the axiom of choice.

Actually, what Feferman-Levy showed was that their model satisfied "$\mathbb{R}$ is the countable union of countable sets," but this implies that $\omega_1$ is singular: in ZF, we can show that there is a (very simply defined) surjection $s:\mathbb{R}\rightarrow\omega_1$, so if $\mathbb{R}$ is the union of countably many countable sets, then so is $\omega_1$. Now let $\omega_1=\bigcup_{i\in\omega} C_i$, where each $C_i$ is countable. Either some $C_i$ is cofinal in $\omega_1$, in which case we're done, or the sequence $\alpha_i=\sup(C_i)$ is cofinal in $\omega_1$, in which case we're also done.

Answer 2

Let me also add something which is implicit in Noah's answer. It is definitely not correct that the countable union of countable sets has cardinality of at most $\aleph_1$.

It is true that if $\bigcup\{A_n\mid n<\omega\}$ can be well-ordered, and each $A_n$ is countable, then the cardinality is at most $\aleph_1$. But it is most certainly possible that the cardinality is not even comparable with $\aleph_1$, and if by countable you allow also finite, then it can even be Dedekind-finite.

What is true, however, is that if you take any function from a countable union of countable sets to the ordinals, then its range must have cardinality of at most $\aleph_1$. Because the image of a countable set is countable, and so we return to the case of a countable union of countable sets which can be well-ordered (the union can).

But wait, there's more! A very old result by Douglass B. Morris, stating the following is consistent with $\sf ZF$:

For every $\alpha$, there is a set $X_\alpha$ which is the countable union of countable sets, such that $\mathcal P(X_\alpha)$ can be mapped onto $\omega_\alpha$.

So there's no real bound on how large, and how odd, a countable union of countable sets can be. Or how strange a universe without choice can be.

---

Let me point out that you are right about the general theorem. It is always possible to arrange that the successor of $\aleph_\gamma$ has cofinality $\aleph_\gamma$, at least when $\aleph_\gamma$ is regular. Or even a countable cofinality if you prefer.

The key point is that just being well-ordered is not enough, one needs to have a distinguished bijection with the cardinal itself. Here is where the axiom of choice is used.

But similar to the countable case, you can prove that the union of $\aleph_\gamma$ sets of cardinality $\aleph_\gamma$, if well-orderable, has cardinality of at most $\aleph_{\gamma+1}$.