Baby Rudin proves that the countable union of countable sets is countable. From reading other proofs online, the axiom of choice has to be invoked; however, I'm not seeing immediately where that is used here.
Theorem 2.12. Let $\{E_n\}$, $n=1,2,...$ be a sequence of countable sets, and put $S= \bigcup_{n=1}^\infty E_n.$ Then S is countable.
Proof. Let every set $E_n$ be arranged in a sequence $\{x_{nk}\}, k=1,2,3,…,$ and consider the infinite array
in which the elements of $E_n$ form the $n$th row. The array contains all elements of S. As indicated by the arrows, these elements can be arranged in a sequence \begin{equation} (17) \ \ \ x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32};… \end{equation} If any two of the sets $E_n$ have elements in common, these will appear more than once in (17). Hence there is a subset $T$ of the set of all positive integers such that $S\sim T$, which shows that $S$ is at most countable. Since $E_1 \subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable.
Does "picking" the elements of each $E_n$ and arranging them in a sequence invoke AC? That doesn't seem right, since then it seems like the classic "$\mathbb{Q}$ is countable" argument would also invoke choice. Is AC hidden in the "there is a subset $T$ of the set of all positive integers such that $S\sim T$, which shows that $S$ is at most countable" part?
Thanks so much. Any help/insight would be really appreciated.
Yes, you need choice in order to pick a particular sequence for each of the $E_n$s -- remember that all you know about them for the purpose of this proof is that at least one sequence exists; this leaves open the possibility that there will be many sequences and no principled way to select one particular among them.
You're given as an assumption that there is some way to arrange each $E_n$ in a row, but what you need in order to construct a bijection $f:\mathbb N\to S$ is that you use the same enumeration of $E_1$ when you define $f(1)$ as when you define $f(3), f(6), f(10)$, and so on. Likewise, you need to use the same enumeration of $E_n$ each time you pick a number from it. It is remembering a particular choice of sequence for each of the infinitely many $E_n$s that requires you to put those choices into a single mathematical object, and then you need the Axiom of Choice to make sure that such an object exists.
You don't run into this problem when showing that $\mathbb Q$ is countable, because there you know enough about the sets that you can specify a particular sequence to use in each case, and therefore there's no need to make arbitrary choices.