In Abbott's "Understanding Analysis," Abbott offers the following idea to run through the proof:
Assume B is a countable set. Thus, there exists a bijection $f:\mathbb{N} \rightarrow B$. Let $A\subseteq B$ be an infinite subset of $B$. We show $A$ is countable. Let $n_1=\min\{n\in \mathbb{N}: f(n)\in A\}$. As a start to a definition for $g: \mathbb{N}\rightarrow A$, set $g(1)=f(n_1)$. Show how to inductively continue this process to produce a bijection $g:\mathbb{N}\rightarrow A$.
I'm not seeing how to inductively continue this process to produce a definition for a bijection. Thanks for the help!
Best Answer
Let $n_2$ be the next $n$ (after $n_1$) such that $f(n) \in A$. Let $g(2):=f(n_2)$. Can you see how to continue?
To prove $g$ is onto, note that $\{g(1),g(2),\dots,g(K)\} = A \cap \{f(1), \dots, f(n_K)\}$. Further, $n_i$ increases strictly and $f$ is onto.