Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
I don't think any form of choice is necessary. Given the enumerations of each of the sets you can construct an enumeration of their union. Or do we have to choose an enumeration for each set? –  WimC Dec 2 '12 at 17:53
3  
@WimC: Yes, we do have to choose an enumeration for each set, and that requires choice. A slightly modified version of your statement "Given the enumerations of each of the sets you can construct an enumeration of their union." is correct: Given one enumeration of each of the sets you can construct an enumeration of their union. The problem is that the fact that the sets are countable doesn't mean that we're given one enumeration for each of them. –  joriki Dec 2 '12 at 17:58
    
@joriki That's what I meant to say: for each set one enumeration is provided. But I see that you can indeed read it differently. Bah, language... ;-) –  WimC Dec 2 '12 at 18:04
add comment

2 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
Reading your answer makes me see how haphazardly I wrote mine (and thank god for that grace period during which edits are not registered, I have used it well). :-) –  Asaf Karagila Dec 2 '12 at 18:17
    
Apparently Russell couldn't tell the difference between left and right boots. That can't have been good for his feet. –  Nate Eldredge Dec 2 '12 at 18:47
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.