Countable unions of countable sets

Question

It seems the axiom of choice is needed to prove, over ZF set theory, that a countable union of countable sets is countable.

Suppose we don't assume any form of choice, and stick to ZF. What are the possible cardinalities of a countable union of countable sets?

Could a countable union of countable sets have the same cardinality as that of the real numbers?

Answer 1

It is a bit hard to answer your first question, since a countable union of countable sets does not even need to be well-orderable. For example, we could have an uncountable set that is the countable union of sets of size $2$. These sets are called Russell cardinals. You may find the following paper interesting:

H. Herrlich and E. Tachtsis, On the number of Russell’s socks or $2 + 2 + 2 + \dots=?$, Comment. Math. Univ. Carolin. 47 (2006), 707-717.

The paper discusses in a fairly self-contained manner the variety of Russell cardinals, and some of their basic properties. As described in the background section of the paper, the name "Russell cardinal" comes from an example due to Russell trying to explain the need for the axiom of choice: If we are given infinitely many pairs of shoes, and asked to pick one of each, we can easily do it since, say, we can pick the left shoes. But if we are given an infinite set of pairs of socks, then it is not clear how to make the choices. Russell's original example, amusingly enough, used boots rather than socks, which kind of makes not much sense, and it is later authors that switched to socks when describing the example.

Anyway, there are many Russell cardinals (at least as many as real numbers!), if there is one at all, and that is just countable unions of pairs.

If we look at countable unions of countable sets, we can have even more possibilities:

• The reals can be a countable union of countable sets. This is a famous example due to Feferman and Levy. On the other hand, the reals cannot be a Russell cardinal, because in any finite set of reals we can always pick one (say, the smallest), so we can easily check that a countable union of finite sets of reals is countable.
• $\omega_1$ can be a countable union of countable sets. In fact, this happens whenever the reals are a countable union of countable sets.
• In a precise sense, there is no bound to the complexity of the sets that can be expressed as a countable union of countable sets. For example, Morris showed that it is consistent to have that for every ordinal $\alpha$ there is an $X$ that is a countable union of countable sets, and there is a surjection from $\mathcal P(X)$ onto $\aleph_\alpha$. (Of course, different $\alpha$ require different $X$.)

This is not to say that there are no limitations. For example, a countable union of countable well-ordered sets has size at most $\omega_1$. It is consistent (by a significant result of Gitik) that any well-ordered cardinal has cofinality $\omega$. This means that $\omega_2$, for example, could be written as a countable union of smaller sets, so as a countable union of countable unions of countable sets. However, it is not itself a countable union of countable sets.

Answer 2

Yes. It is consistent that the real numbers are a countable union of countable sets. For example in the Feferman-Levy model this is true. In such model $\omega_1$ is also the countable union of countable sets (and there are models in which $\omega_1$ is the countable union of countable sets, but the real numbers are not).

It is consistent [relative to large cardinals] that $\omega_1$ is the countable union of countable sets, and $\omega_2$ is the countable union of countably many sets of size $\aleph_1$, that is $\omega_2$ is the countable union of countable unions of countable sets.

Indeed it is consistent [relative to some large cardinal axioms] that every set can be generated by reiterating countable unions of countable sets.

For non-aleph cardinals the follow results holds:

Let $M$ be a transitive model of ZFC, there exists $M\subseteq N$ with the same cardinals as $M$ [read: initial ordinals] and the following statement is true in $N$:

For every $\alpha$ there exists a set $X$ such that $X$ is a countable union of countable sets, and $\mathcal P(X)$ can be partitioned into $\aleph_\alpha$ nonempty sets.

D. B. Morris, A model of ZF which cannot be extended to a model of ZFC without adding ordinals, Notices Am. Math. Soc. 17, 577.

Note that $\mathcal P(X)$ can only be mapped onto set many ordinals, so this ensures us that there is indeed a proper class of cardinalities which can be written as countable unions of countable sets.

---

Some positive results are:

1. If $X$ can be expressed as the countable union of countable sets, and $X$ can be well-ordered then $|X|\leq\aleph_1$.

2. If $\langle A_i,f_i\rangle$ is given such that $A_i$ is countable and $f_i\colon A_i\to\omega$ is an injection, then $\bigcup A_i$ is countable.

3. The collection of finite subsets of a countable set, as well finite sequences are both countable, without the use of the axiom of choice (so there are still only a countable collection of algebraic numbers in $\mathbb R$).