Countability of Countable Union of Countable Sets Requires Countable Choice

The union of a bunch of countable sets is usually countable. This is very obvious if there are finitely many sets, say A, B, C. Pick an order for each set A={A1, A2, A3, ...} and then you can use the obvious ordering

1. A1
2. B1
3. C1
4. A2
5. B2
6. C2
7. A3
8. B3
9. C3
10. ...

So the finite union of countable sets is countable. So far so good.

But what if you have infinitely many countable sets to union together? If there are countably many sets, you might think of the elements of the union in a sort of lattice arrangement and trace the diagonals:

1. A1
2. A2
3. B1
4. A3
5. B2
6. C1
7. A4
8. B3
9. C2
10. D1
11. ...

It would take a little more work to write a closed form expression for what number goes with which element, but every element of every set gets covered eventually. It's obvious, right?

I sure thought so. I have used this principle fairly frequently throughout my schooling assuming it was a straightforward principle. Speaking with several other math folks, no one seemed to be aware of a subtle problem: each set is countable, meaning each set has a bijection with the natural numbers (there is at least one way to enumerate the elements of each set). We could also say that for each set, there is a non-empty set of bijections with the natural numbers.

The problem is that, picking one element (bijection/enumeration) from each of infinitely many sets (the sets of ways to enumerate the elements of our sets) is not always possible under the ZF axioms. In other words, since all you know is that it is possible to enumerate each of the sets, the normal assumptions about math don't let you assign an enumeration to each of infinitely many things. It requires a special assumption called the axiom of choice (or the weaker "countable choice" for the case of a countable collection of sets).

So be warned! You must not assume willy-nilly that the countable union of countable sets is countable. You must include countable choice with your other assumptions.

If you're still interested, I recently found this interesting discussion of the problem:
https://www.dpmms.cam.ac.uk/~tf/cupbook3AC.pdf