My question of more of a sanity check for reading comprehension in Rudin's text. Here is a quick overview of Rudin's proof for the theorem 2.13:
Theorem 2.13. Let $A$ be a countable set, and let $B_n$ be the set of all $n$-tuples $\left(a_1,\dots,a_n\right)$, where $a_k\in A$ ($k=1,\dots,n$), and the elements $a_1,\dots,a_n$ need not be distinct. Then $B_n$ is countable.
Proof. That $B_1$ is countable is evident since $B_1=A$.
Suppose $B_{n-1}$ is countable ($n=2,3,4,\dots$). The elements of $B_n$ are of the form
$$
\left(b,a\right), \qquad\left(b\in B_{n-1},a\in A\right).
$$
For every fixed $b$, the set of pairs $\left(b,a\right)$ is equivalent to $A$, and hence countable. Thus $B_n$ is the union of of a countable set of countable sets.
I understand everything else in the proof except the bolded sentence. What is the union expression for $B_n$, i.e. what are the sets that we are combining in the union? Reader is given the information that all $B_k$, $k = 1,\dots,n$ are countable, but this can't surely mean that $B_n$ is the union of the other $B_k$ sets, as $B_n$ contains all $n$-tuples?
Best Answer
The proof is by induction. The first sentence is the base case ($B_1$ is countable). The rest of the proof establishes the induction step.
The countable sets Rudin is referring to are the sets
$$C_b=\{(b,a)|a \in A\}$$
for every $b \in B_{n-1}$. There is a bijection from each of these sets $C_b$ to $A$, so each $C_b$ is countable.
Moreover, there is exactly one $C_b$ for every $b \in B_{n-1}$. Since $B_{n-1}$ is countable by the induction hypothesis, this means there are countably many $C_b$.
Finally, there is a bijection from $\displaystyle \bigcup_{b \in B_{n-1}} C_b$ to $B_n$. Since this union is a countable union of countable sets, it follows that $B_n$ is countable.
For an explicit example, we could consider going from $n=2$ to $n=3$, with $A$ the natural numbers $\mathbb{N}=\{1,2,3,\dots\}$. We have the sets. By the induction hypothesis, we've already shown that the set $\mathbb{N}^2=\{(1,1),(1,2),\dots,(2,1),(2,2),\dots\}$ is countable. We now look at the sets
\begin{align*} C_{(1,1)}&=\{((1,1),1),((1,1),2),((1,1),3),\dots\}\\ C_{(1,2)}&=\{((1,2),1),((1,2),2),((1,2),3),\dots\}\\ &\vdots\\ C_{(2,1)}&=\{((2,1),1),((2,1),2),((2,1),3),\dots\}\\ C_{(2,2)}&=\{((2,2),1),((2,2),2),((2,2),3),\dots\}\\ &\vdots \end{align*}
Each of these sets has $\mathbb{N}$-many elements, so they're all countable. Also, there are $\mathbb{N}^2$-many of these sets, so there are countably many of them.
Finally, the union of all these sets is the set $\{((\ell,m),n)|\ell,m,n \in \mathbb{N}\}$. There is a bijection from this set to $\mathbb{N}^3$: its the map $((\ell,m),n) \mapsto (\ell,m,n)$. So $\mathbb{N}^3$ is also countable.