If I have $\kappa$ countable sets, when their union is not countable? only if $\kappa$ is uncountable? Using AC make differences?

  • $\begingroup$ If $\kappa\le\omega$, then the union of $\kappa$ many countable sets is still countable (without using the axiom of choice). For the case $\kappa>\omega$, can we assume that the sets are disjoints, or different? We can have $2^\omega$ different subsets of $\omega$, say, their union is still countable.. $\endgroup$ – Berci Jun 1 '13 at 17:34
  • 2
    $\begingroup$ Choice definitely plays a role. It is possible (without choice) for a countable union of finite sets (in fact, sets of size $2$) to be uncountable. See here for some details. $\endgroup$ – Andrés E. Caicedo Jun 1 '13 at 17:39
  • 1
    $\begingroup$ @Berci, you may want to update your comment. $\endgroup$ – vadim123 Jun 1 '13 at 17:47
  • $\begingroup$ @Andres: The link is broken. There is some extra letters after the "pdf". $\endgroup$ – Asaf Karagila Jun 1 '13 at 17:49
  • 3
    $\begingroup$ Fixed link: here. $\endgroup$ – vadim123 Jun 1 '13 at 17:50

I'm assuming through the post that the sets $A_i$ are pairwise disjoint. Otherwise it is trivial to generate a family of $2^{\aleph_0}$ sets whose union is countably infinite.

If we assume the axiom of choice then $|\bigcup_{i\in I} A_i|=|I|\cdot\sup\{|A_i|\mid i\in I\}$. If we assume that $|A_i|=\aleph_0$ for every $i\in I$, then indeed this means that the union is uncountable if and only if $I$ is uncountable.

Not assuming the axiom of choice one can get many different kind of strange behaviors.

  1. It is consistent that the countable union of pairs is uncountable (in the sense that it has no countable subset, but also it is possible that it has).
  2. It is consistent that countable union of finite sets is countable, but there is a countable set of countable sets whose union is uncountable.
  3. It is consistent that $\sf DC_\kappa$ holds, for some infinite $\kappa$, which assures us that things behave normally up to unions of $\kappa$ sets. But at the same time there is a family of $\kappa^+$ pairs whose union is uncountable (and we can instead make those pairs into countably infinite sets at cetra).
  4. It is even consistent that the countable union of countable sets has cardinality $\aleph_1$, which in contrast to the previous examples -- is a well-ordered cardinal.

    At the same breath, one should mention it is consistent to have the countable union of countable sets with the cardinality of $2^{\aleph_0}$, but in that case $\Bbb R$ cannot be well-ordered.

However one thing is provable without the axiom of choice:

Suppose that the union of $A_i$ is countable, then:

  1. $I$ is countable (or finite), and
  2. $A_i$ is countable (or finite) for every $i\in I$.
  • $\begingroup$ what is $\sf{DC}_\kappa$? $\endgroup$ – MphLee Jun 1 '13 at 19:55
  • 1
    $\begingroup$ @MphLee: It's a weak form of choice which is equivalent, essentially, to the statement "If $(P,\leq)$ is a partially ordered set such that every well-ordered chain has order type $<\kappa$, and has an upper bound, then there is a maximal element.", this is similar to Zorn's lemma, only we require that the [well-ordered] chains are not "too long". $\endgroup$ – Asaf Karagila Jun 1 '13 at 20:03

I have just been explaining to my 12-year-old daughter that you can count the squares in an infinite grid - for example by counting in a spiral. (She had a project on understanding the mathematics of a famous mathematician - so we chose the Cantor Diagonal Argument).

So you can count the squares in a quarter-grid, which is a subset of the infinite grid. You can count along diagonals, for example, or along the part of the spiral which survives. It doesn't matter what you put in the squares - if it fits in the grid you can count it, so you can put your first sequence in the first row, the second sequence in the second row - because the sequences are countable, each sequence fits in a row. The number of sequences is countable, so there are enough rows for all of them.

The only complication which arises is if there are repeated elements counted more than once, but those can be negotiated ...

  • 3
    $\begingroup$ Actually, the real complication starts when there is more than one way to order the sets, and no uniform choice for the orders... $\endgroup$ – Asaf Karagila Jun 1 '13 at 17:53
  • 1
    $\begingroup$ @AsafKaragila Thanks. I was, of course, assuming that each countable set came with a predetermined order, and the sets were ordered before I had to enter them in my grid. This assumption need not be valid, and that does get more interesting. I'll not be explaining it to my daughter tonight though. $\endgroup$ – Mark Bennet Jun 1 '13 at 17:59
  • 2
    $\begingroup$ That may cause nightmares! :-) When I was finishing my M.Sc. thesis last summer I went into overdrive and started having dreams about the axiom of choice and the set theoretical universe. Needless to say, I didn't sleep very well for most of that summer. $\endgroup$ – Asaf Karagila Jun 1 '13 at 18:09

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.