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.

  • $\begingroup$ Let $W_n$ be the set of well-orderings of $A_n.$ If $P=\prod_{n\in \omega}W_n\ne \phi$ then it's easy. But without Countable Choice we can't prove that $P\ne \phi.$... It's consistent with ZF that there is a pair-wise disjoint family $A=\{a_n:n\in \omega\}$ of two-member sets, such that $\cup A$ cannot be well-ordered (Hence $\cup A$ and $\omega$ are cardinally incomparable) . Called a "sock set". ("The Axiom of Choice is needed for (pairs of) socks but not for (pairs of) shoes'"--Bertrand Russell.) $\endgroup$ – DanielWainfleet Oct 4 '17 at 10:06

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.

  • 1
    $\begingroup$ Nowadays I'd send someone to Ioanna Dimitriou's master or Ph.D. thesis for a review of the Feferman–Levy model; or to Arnie Miller's paper about long Borel hierarchies, for a quick and dirty overview. $\endgroup$ – Asaf Karagila Oct 4 '17 at 11:48
  • $\begingroup$ Even more interestingly than a surjection $s\!:\mathbb R\to\omega$, there is one onto $\omega_1$. :-) $\endgroup$ – Andrés E. Caicedo Oct 4 '17 at 13:38
  • $\begingroup$ @AndrésE.Caicedo Hey, I wasn't wrong! Fixed. $\endgroup$ – Noah Schweber Oct 4 '17 at 13:40

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


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.