# Proof that an infinite subset of $\mathbb{N}$ is countable [duplicate]

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:

1. Is what I wrote correct?
2. If so, how do you prove that $f$ is actually a function from $A$ to $\mathbb{N}$ and is also a bijection?
• By $\min{A_{n-1}}$ do you mean $\min( A_0,..., A_{n-1})$?
– Paul
Apr 18, 2015 at 14:16
• I mean the smallest element of the set of natural numbers $A_{n-1}$ Apr 18, 2015 at 14:19

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.

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.

• @Paul There always is: it's one of the most important characteristics of the natural numbers, and one that allows us to use mathematical induction, for example. Apr 18, 2015 at 14:19
• This is my idea. I just wanted to avoid using "etc." and actually define a function and prove its bijectivity. Apr 18, 2015 at 14:21
• @Nicol If you mean an explicit function I can't see how is this possible as we're not given an explicit subset $\;A\subset \Bbb N\;$ ... Apr 18, 2015 at 14:23
• Nope, not an actual numerical expression, but a function like the one I defined, which I think expresses formally the idea of putting the elements of $A$ in increasing order. Apr 18, 2015 at 14:25
• @Nicol I see... Yet you're defining a function to the naturals but not on $\;A\;$ but rather on its power set $\;P(A)\;$ . I'm not sure this will work. Apr 18, 2015 at 14:31

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$