While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem:
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$. (pause)
Okay, from the theorem's statement, I can see that $B_1=\left\{a_1:a_1\in A\right\}=A$ (assuming $\left(a_1\right)=a_1$). So far so good.
(continue) 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).\text{ (pause)}
$$
This makes sense because $B_n$ differs from $B_{n-1}$ in the sense that $B_n$ has an additional element, $a$. Now, this is what throws me off:
(continue) For every fixed $b$, the set of pairs $\left(b,a\right)$ is equivalent to $A$. (pause)
I am going to end right here. How is this true? I mean, if I take $b\in B_1$, then $\left(b,a\right)$ is a $2$-tuple, and $A$ has no element that is a $2$-tuple.
What am I missing?
Best Answer
Fix any $b\in B_{n-1}$, and let $S_b=\{\langle b,a\rangle:a\in A\}$; the assertion is that $S_b$ is equivalent to $A$. By this he means simply that there is a bijection between $S_b$ and $A$, and it’s easy to describe one: the map
$$f_b:S_b\to A:\langle b,a\rangle\mapsto a$$
is such a bijection.