Proof that an infinite subset of $\mathbb{N}$ is countable I want to prove that if $A$ is an infinite subset of the natural numbers, then it is countable. 
I thought of an informal proof: put the elements of $A$ in increasing order. Then associate the smallest to $1$, the second smallest to $2$, the third smallest to $3$ and so on. 
I've tried to formalise this proof in this way: consider the sequence $$ \begin{cases} A_1=A \\ A_n=A_{n-1}-\min{A_{n-1}}\end{cases}$$
The function $f(\min{A_n})=n$ has domain $A$ and codomain $\mathbb{N}$ and is a bijection, therefore $A$ is countable.
My questions are the following:


*

*Is what I wrote correct?

*If so, how do you prove that $f$ is actually a function from $A$ to $\mathbb{N}$ and is also a bijection? 

 A: I'd rather use the well known and comfortable property of the natural numbers of being a well ordered set:
First, let $\;a_1\in A\;$ be the smallest (wrt the usual order) element in $\;A\;$
Now, let $\;a_2\in A\setminus\{a_1\}\;$ be the smallest element, etc.
A: Let me write down a rigorous definition of a bijection $f : \mathbb{N} \to A$.
Claim: For each integer $n \ge 1$ there exists a function
$$f_n : \{1,\ldots,n\} \to A
$$
such that for each $i=1,\ldots,n$, the least element of $A - \{f_n(j) \bigm| 1 \le j < i\}$ is $f_n(i)$.
The proof of this claim is by induction on $n$.
Basis step: The function $f_1 : \{1\} \to A$ is defined by $f_1(1) =$ the least element of $A$.
Induction step: Suppose that $n \ge 2$ and that the function $f_{n-1}$ exists. Define the function $f_n$ so that its restriction to $\{1,\dots,n-1\}$ equals $f_{n-1}$, and so that $f_n(n) =$ the least element of $A - \{f_{n-1}(1),\ldots,f_{n-1}(n-1)\}$.
QED Claim.
Now define $f : \mathbb{N} \to A$ by $f(n) = f_n(n)$.
Okay, so, it still remains to prove rigorously that $f$ is a bijection. Here I'll punt, and say that what one does to accomplish this are further induction proofs. For instance, one proves that for each $n \in \mathbb{N}$, the least element of $A - \{f(i) \bigm| 1 \le i < n\}$ is $f(n)$. Injectivity and subjectivity follow.
A: I am also trying to formalize this proof to my taste and I do so with an equally shared distaste for "etc."  Here is what I have so far...
Let $A \subset \mathbb{N}$ be infinite.  Let $\mathbb{N}_k$ denote $\{0,1,...,k-1\}$. Suppose $f:A \rightarrow A$ is defined by the rule, $n  \mapsto \min(A \setminus \mathbb{N}_{n+1})$. We know that this minimum always exists since $\mathbb{N}$ is well-ordered and $A \setminus \mathbb{N}_k$ is never empty (because if it is for some $k$, then $A$ could not be infinite). So, $f$ is well-defined. Less formally, we can say that $f$ maps each number in $A$ to its immediate successor in $A$. Therefore, $n < f(n)$ for all $n \in \mathbb{N}$. 
By the Recursion Theorem, there exists a unique function $F: \mathbb{N} \rightarrow A$ such that:
$$F(0) = \min(A) \\
F(k + 1) = f(F(k))$$
for any $k ∈ \mathbb{N}$. Since $F(k) < f(F(k)) = F(k+1)$, $F$ is injective. Since $\iota:A \rightarrow \mathbb{N}$ is also injective, $A \sim \mathbb{N}$ by the Schroeder-Bernstein Theorem.  $\square$
