# Proving that existence of injection $f : S\to \mathbb{N}$ implies $S$ is countable?

How does one formally prove that if there exists an injective function $$f:S \rightarrow \mathbb{N}$$ then $$S$$ is countable? If there exists an injective function $$f:S \rightarrow \mathbb{N}$$ then there exists a bijection $$g:S \rightarrow f(S)$$ and $$f(S)\subseteq \mathbb{N}$$ is a countable set. But the definition of countable set requires a bijection from $$\mathbb{N}$$ to $$S$$? What is missing here?

• First of all $S$ may be finite. Second, if it infinite, use Schröder–Bernstein theorem Jan 29 at 4:44
• @markvs There is no need to use Shroeder-Bernstein one can come up with a bijection quite easily in the infinite case. Jan 29 at 5:52
• @Logic: Schröder–Bernstein in this case (one set is countable) is easy enough. You are just suggesting to repeat their proof without mentioning their names. Jan 29 at 5:55
• @markvs How are you going to show the injection between N and S ? Jan 29 at 7:47
• Every infinite set contains a copy of $\Bbb N$ basically by the definition of "infinite". Jan 29 at 11:42

The definition of countable is that a set is countable precisely when there is a bijective map from it to a subset of the natural numbers. See for example wikipedia.

The more interesting question, which is what I think you really mean to ask, is to show that any countable set is either finite, or there is a bijective correspondence between it and $$\mathbb{N}$$.

Suppose we have an injective map $$f\colon S\to \mathbb{N}$$. Suppose that $$S$$ is not finite. We will construct a bijection $$g\colon \mathbb{N}\to S$$.

Firstly we describe an inductive process for picking elements $$s_0,s_1,s_2,\cdots\in S$$.

We know $$f(S)$$ is not empty, as $$S$$ is not finite (hence not empty), and given $$s\in S$$ we have $$f(s)\in f(S)$$. By the well-ordering principle we may pick $$x\in S$$ minimal in $$f(S)$$. As $$f$$ injective, there is a unique $$s_0\in S$$ such that $$f(s_0)=x$$.

Once $$s_0,s_1,\cdots,s_{i-1}\in S$$ have been selected, we select $$s_i\in S$$ as follows. The set: $$X_i=\{x\in f(S)| x>f(s_{i-1})\},$$ is non-empty, as otherwise the image of $$f$$ would be a finite set, so $$S$$ would be finite. By the well-ordering principle we may pick $$x\in X_i$$ minimal. As $$f$$ injective, there is a unique $$s_i\in S$$ with $$f(s_i)=x$$.

Now we claim the function $$g\colon \mathbb{N}\to S$$ mapping $$i\mapsto s_i$$ is bijective.

Note that by construction, for $$i>0$$ we have $$f(s_i)\in X_i$$ so $$f(s_i)> f(s_{i-1})$$. Then by induction on the size of $$j-i$$, we have if $$j>i$$ then $$f(s_j)>f(s_i)$$. Thus $$g$$ must be injective.

Now pick an arbitrary $$s\in S$$. To show that $$g$$ is surjective, we must show that $$s=s_i$$ for some $$i\in \mathbb{N}$$. We know $$f(s_i)$$ is an increasing sequence, so for some $$j\in\mathbb{N}$$, we have $$f(s_j)>f(s)$$, so $$f(s)\notin X_j$$.

To complete our proof we will prove by induction that for $$j>0$$:$$f(S)=\{f(s_0),f(s_1),\cdots,f(s_{j-1})\}\cup X_j$$

Thus we have that $$f(s)=f(s_i)$$ for some $$i and $$s=s_i$$.

We selected $$f(s_0)$$ minimal in $$f(S)$$, so for every element $$x\in f(S)$$, either $$x=f(s_0)$$ or $$x>f(s_0)$$ so $$x\in X_1$$:$$f(S)=\{f(s_{0})\}\cup X_1$$

For the inductive step, we need only note that we selected $$f(s_{i-1})$$ minimal in $$X_{i-1}$$, so any element of $$X_{i-1}$$ is either $$f(s_{i-1})$$, or greater than $$f(s_{i-1})$$, so lies in $$X_i$$: $$X_{i-1}=\{f(s_{i-1})\}\cup X_i\qquad\qquad (1)$$ Thus for $$i\geq 2$$: $$\begin{eqnarray*}f(S)&=&\{f(s_0),f(s_1),\cdots,f(s_{i-2})\}\cup X_{i-1}\\&=&\{f(s_0),f(s_1),\cdots,f(s_{i-2})\}\cup \{f(s_{i-1})\}\cup X_i\end{eqnarray*}$$ Here the first equality comes from the inductive hypothesis, and the second equality comes from $$(1)$$.

• (+1) for writing it all out, my point to markvs is that constructing an injection between N and S is pretty much as hard as constructing the bijection in the infinite case, so there is no need to use the shroeder bernstein theorem. I hope you agree? Jan 29 at 8:14
• @Logic It is a similar construction, where you keep picking $s_i$ inductively, but you do not need to worry about surjectivity so you save a bit there. Once you add all the back and forth of the schroder bernstein theorem I think you are doing more work than the direct approach. My only hesitation is that someone might find a way of saying that my argument essentially follows schroder bernstein. I do not see it though.
– tkf
Jan 29 at 12:01
• Yes that was my point, it seems markvs belivies that its trivial to take out a copy of N from an infinite set, but does not realise that this actually isnt true in ZF and needs (a little) choice!! Jan 29 at 12:06
• That makes sense. Whereas in the above approach we do not have to make choices, as we use the original map $f$ to distinguish a minimal element not already picked.
– tkf
Jan 29 at 12:11