This question already has an answer here:

Why can't I use this proof to prove that the countable union of countable sets is countable without the axiom of countable choice?

Take the set of integers; some proper subset of it, call it $A$, can be mapped, with $f$, a 1-1 and onto function, to the set of even integers.

Some proper subset of the set of even integers, call it $B$, can be mapped, with $g$, a 1-1 and onto function, to the integers. Take the subset of $A$, call it $C$, which is mapped, with the use of $f$, to $B$ which is mapped, with the use of $g$, to the set of integers. Then find the subset of $A$ which is mapped, in a similar fashion, to $C$. Continue doing this forever.

Each one of these sets is countable, given that that they map to $A$ in a 1-1 and onto fashion.

We can find a countable amount of them (just keep doing the same thing). They are all subsets of $A$ and so their union is a subset of $A$.

One can therefore easily show, using the Cantor Bernstein Theorem, that they have the same carnality as $A$. We can easily show that every union of countable sets can easily be placed in a 1-1 and onto fashion with this specific union of countable set.

I assume that I never used the Axiom of Countable Choice in this proof, so what is the problem?


marked as duplicate by Asaf Karagila elementary-set-theory Feb 5 '16 at 6:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Your assumption is incorrect. $\endgroup$ – Andrés E. Caicedo Feb 5 '16 at 5:41
  • 2
    $\begingroup$ How does the last part work? "We can easily show that every [countable] union of countable sets can easily be placed in a 1-1 and onto fashion with this specific union of countable set." $\endgroup$ – Chris Culter Feb 5 '16 at 5:44
  • $\begingroup$ Also, how are you proving CBS? $\endgroup$ – Stella Biderman Feb 5 '16 at 5:54
  • $\begingroup$ Please use paragraphs. $\endgroup$ – YoTengoUnLCD Feb 5 '16 at 6:18
  • $\begingroup$ I'm proving CBS in any way that does not require ACC, and I'm told that many do not. My countable sets are disjointed (each one of them from the other). So take the countable union you are trying to examine and take every set which was put together to create this union. Take a 1-1 and onto map from those sets to the sets which created the union in my uncountable union. Now, the union created by the sets you are examining should have a 1-1 function to my union. Does this require ACC? Which assumption? $\endgroup$ – Yitzchak Shmalo Feb 5 '16 at 6:20

Suppose $\{A_i\}$ are a countable family of countable sets and $\{B_i\}$ partition the integers into countably many disjoint countably infinite subsets. You're right that the construction of $B_i$ doesn't necessarily use choice. But let's talk about the truly important map - the injection from $\cup A_i$ into $\cup B_i$, which will show that $\cup A_i$ is countable.

Assume the $A_i$ are disjoint for simplicity. How can we create this injection?

Start by injecting $A_1$ into $B_1$, which is possible since both are countable. Well, there are a bunch of ways of doing this. We need to pick one. There's no canonical/best choice. Call it $f_1$. Then inject $A_2$ into $B_2$. We have to pick another injection $f_2$ for this. Then the union of the maps $f_i$ gives us the injection that we want. But despite the fact that each $f_i$ is individually guaranteed to exist, we still have to pick a particular injection for each index $i$. This requires the axiom of countable choice (more precisely, you need an element from the infinite product of the sets $\{g: g$ is an injection from $A_i$ to $B_i$$\}$).


Given a partition N into pairwise disjoint infinite subsets $\{S_j:j\in N\}$ and given a family $\{T_j:j\in N\}$ of countable sets, there exists, for each $j\in N,$ an injective map $f_j:T_j \to S_j.$ (And if $S_j\ne \phi$ there are many such maps.)But then you want to assert the existence of a sequence $(f_j)_{j\in N}$ of such maps. This requires Countable Choice . Consider, for each $j\in N,$ the set $I_j$ of injections from $T_j$ into $S_j.$ We have $\forall j\in N \;(I_j\ne \phi).$ But you need a Choice-function $\psi:N\to \cup_{j\in N}I_j$ such that $\forall j\in N\;(\psi (j)\in I_j).$ Then can you obtain a sequence $(f_j)_{j\in N}=(\psi (j))_{j\in N}$. Conversely, given the desired sequence $(f_j)_{j\in N},$ you obtain a Choice-function $\psi$ by defining $\psi (j)=f_j$ for all $j\in N.$

  • $\begingroup$ I do not think this requires choice (in my case). $\endgroup$ – Yitzchak Shmalo Feb 5 '16 at 6:30
  • 1
    $\begingroup$ Saying "continue doing this forever" is not logical . It is a way of organizing your thoughts, to express the intention of acquiring some infinite sequence of maps. But what is a sequence? Write out a def'n of this object called a sequence. $\endgroup$ – DanielWainfleet Feb 5 '16 at 22:13

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