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?

  • 1
    $\begingroup$ First of all $S$ may be finite. Second, if it infinite, use Schröder–Bernstein theorem $\endgroup$
    – markvs
    Jan 29, 2022 at 4:44
  • 1
    $\begingroup$ @markvs There is no need to use Shroeder-Bernstein one can come up with a bijection quite easily in the infinite case. $\endgroup$ Jan 29, 2022 at 5:52
  • $\begingroup$ @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. $\endgroup$
    – markvs
    Jan 29, 2022 at 5:55
  • $\begingroup$ @markvs How are you going to show the injection between N and S ? $\endgroup$ Jan 29, 2022 at 7:47
  • $\begingroup$ Every infinite set contains a copy of $\Bbb N$ basically by the definition of "infinite". $\endgroup$
    – markvs
    Jan 29, 2022 at 11:42

1 Answer 1


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.

Therefore your question is answered immediately by definition.

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 f(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)<f(s_{j})$, which is minimal in $X_j$, 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<j$ 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)$.

  • $\begingroup$ (+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? $\endgroup$ Jan 29, 2022 at 8:14
  • $\begingroup$ @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. $\endgroup$
    – tkf
    Jan 29, 2022 at 12:01
  • $\begingroup$ 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!! $\endgroup$ Jan 29, 2022 at 12:06
  • $\begingroup$ 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. $\endgroup$
    – tkf
    Jan 29, 2022 at 12:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .