# Theorem A: subset of a countable set is countable.

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.

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…

• The proof that was posted in the original question is terribly formulated and I can understand very well that it's hard to understand. Why don't they write it directly like you do! :-) By the way, there are for sure simpler proofs for this rather trivial statement.
– Luke
Commented Jul 25, 2018 at 11:37
• @Luke Thank you for the compliment. Commented Jul 25, 2018 at 11:38

Let $B=\{b_1,b_2,b_3,b_4,b_5\}$ and $A=\{b_2,b_4,b_5\} \subset B$. Also let $f:\{1,2,3,4,5\} \longrightarrow B$ be given by $f(i)=a_i$. Then $g(1)=2$ because $f(2)=a_2$ is the first element in $A$.

$A \subset B$, $B$ is finite, $A,B \not = \emptyset$.

There is a bijection $f : I_n \rightarrow B$, where $I_n =${$1,2,3,...,n$}.

We have $B=${$f(1),f(2),...,f(n)$}, or written as a sequence $f_i:=f(i)$, $i=1,2,...n.$

Start to sort out:

Choose the smallest index

$i \in$ {$1,2,..,n$} with $f(i) \in A.$

Call the index $i_1$, i.e $f(i_1) \in A$,

in terms of $g$: $g(1):=i_1$

If $A=${$f(i_1)$} we are done, else

we continue and look at: $B$ \ {$f(i_1)$}.

Proceed likewise find $g(2):= i_2 >i_1$,

where $f(i_2) \in B$ \ {$(f_1)$}, and $f(i_2) \in A.$

The inductive procedure comes to an end after at most $n$ selections.

Say, you have $k$ selections, $1 \le k \le n$, then

$A=${$f(i_1),f(i_2),...f(i_k)$},

where $f_{i_s}=f(i_s)$, with $1 \le s \le k$ is a finite subsequence.

Note $i_1< i_2 < ......<i_k$.

Define $g: I_k \rightarrow$ {$i_1,i_2,....i_k$},

$g(s)= i_s$, where $1 \le s \le k$.

Finally:

$f \circ g$ is a bijection from $I_k \rightarrow A$.

The number $g(1)$ is defined as the minimum of the set $\{ j\in \{1,\ldots ,n\} | f(j)\in A\}$. This set is a subset of $\mathbb{N}$ which is not empty (because $A$ is not empty and $f$ is surjective), so the minimum indeed exists.

As for the second point, if $A=\{f(g(1))\}$, then $A$ is a set that contains only one element, so it surely is countable.

(Note that indeed, in any case, $f(g(1))$ is an element of $A$, by very definition of the number $g(1)$.)