2.8: Every infinite subset of a countable set $A$ is countable.
Proof Suppose $E \subset A$, and $E$ is infinite. Arrange the elements of $x$ of $A$ in a sequence $\{x_{n} \}$ of distinct elements. Construct a sequence $\{n_{k} \}$ as follows: Let $n_{1}$ be the smallest positive integer such that $x_{n_{1}} \in E$. Having chosen $n_{1}, … n_{k-1} (k = 2, 3, 4, …)$, let $n_{k}$ be the smallest integer greater than $n_{k-1}$ such that $x_{n_{k}} \in E$.
When I read this proof for the first time, I didn’t understand how the sequence $ n_k $ was constructed. I mean, how can one be sure of the existence of this sequence? One might say that because $E$ is infinite, it must have an infinite subset, but this is the statement itself!
In other words, I always think that this theorem proves itself or something like "The statement $A$ will be proved using the statement $A$".
Best Answer
Because $A$ is countable, we know that there is a bijection between $A$ and $\mathbb{N}$, or in other words we can write out the elements of $A$ in a list $x_1, x_2, x_3, \ldots$ such that for any $a \in A$ we can find $i \in \mathbb{N}$ such that $a = x_i$.
Then, we use the fact that $\mathbb{N}$ is a well-ordered set, or in other words any non-empty subset of $\mathbb{N}$ has a least element. So therefore we can take the set $\{i \in \mathbb{N} : x_i \in E\}$, and we know that there must be a smallest value of $i$. Building from that, we can construct the sequence of sets $S_k := \{ i \in \mathbb{N} : x_i \in E \land i > n_{k-1}\}$, where $n_k$ is the smallest element of $S_k$.
Then all that's left to do is show that every element of $E$ has a corresponding $n_k$, but since $E \subset A$ we know that each element corresponds to some $x_i$, and if you also show that $n_k \geq k$ it's only a few steps to showing that $x_i$ must in fact be $x_{n_k}$ for some $n_k \leq i$.