Subsets of N are Countable (3.3.6)

Hrbacek and Jech Introduction to Set Theory, chapter 3, section 3, exercise 6:

Let $X⊆ℕ$; prove there exists a one-to-one sequence $f$ onto $X$.

Proof: Let $X$ be nonempty; then let $a∈X$ be the least element of $X$. We define the sequence $f$ by$$f_0 = a$$$$f_{n+1}=g(f_n,n)$$where $g(x,n)$ is the least element of $\{y∈X~|~y > x\}$ when it exists (cf. 3.3.5). Now, we let $P(n)$ be the proposition: if $n∈X$, then $n=f_m$ for some $m∈ℕ$. We shall prove it by total induction. Let $k∈X$. If $X∩k$ is empty, then $k$ is the least element of $X$ and $k=f_0$; otherwise let $p$ be the largest element of this bounded subset. We see $k > p$, and if $r > p$ then $r∉X∩k$ and hence either $r ≥ k$ or $r∉X$, implying $k$ is the least element of $\{y∈X~|~y > p\}$, i.e. $k=g(p,n)$ for all $n∈N$. Since $k > p$ we have $p=f_m$ for some $m$ and now $k=f_{m+1}$. Hence $\text{ran }f=X$.

We shall now prove by double induction (cf. 3.2.13) that $m < n$ and $f_m,f_n$ existing implies $f_m < f_n$, so $f$ is one-to-one. If $n = 0$ then the case is vacuous, so let $n=k+1$ with $m≤k$. If $m=k$ then $f_m < f_n = f_{m+1}$ by the definition of $f$. If $m < k$ then by inductive assumption $f_m < f_k < f_{k+1} = f_n$ and now $f_m < f_n$. This completes the induction and the proof.$~\square$