Theorem 3 A subset of a countable set is countable. In particular, every set of natural numbers is countable.
Proof Let $B$ be a countable set and $A$ a nonempty subset of $B$. First consider the case that $B$ is finite. Let $f$ be a one-to-one correspondence between $\{1,\dots,n\}$ and $B$. Define $g(1)$ to be the first natural number $j$, $1\le j\le n$, for which $f(j)$ belongs to $A$. If $A=\{f(g(1))\}$ the proof is complete since $f\circ g$ is a one-to-one correspondence between $\{1\}$ and $A$. Otherwise, define $g(2)$ to be the first natural number $j$, $1\le j\le n$, for which $f(j)$ belongs to $A\sim\{f(g(1))\}$. The pigeonhole principle tells us that this inductive selection process terminates after at most $N$ selections, where $N\le n$. Therefore $f\circ g$ is a one-to-one correspondence between $\{1,\dots,N\}$ and $A$. Thus $A$ is finite.
Can you elaborate on the statement "Define $g(1)$ to be the first natural number $j$, $1\le j\le n\dots$
I also don't understand the next sentence "If $A=\{f(g(1))\}$, the proof is complete."
I really appreciate if you explain these in easy terms.
Best Answer
The function $f$ is a bijection from $\{1,2,\ldots,n\}$ onto $B$. Since $A\subset B$, there are some elements $k\in\{1,2,\ldots,n\}$ such that $f(k)\in A$. The author calls $j$ to the first such element of $\{1,2,\ldots,n\}$ and then he defines $g(1)=j$. By this definition, $f\bigl(g(1)\bigr)=f(j)\in A$. Does it happen that $A=\bigl\{f\bigl(g(1)\bigr)\bigr\}$? If so, then we're done: $g$ is a bijection from $\{1\}$ onto $A$. Otherwise, we start all over again: let $j'$ be the second element of $\{1,2,\ldots,n\}$ such that $f(j')\in A$, let $g(2)=j'$, and so on…