# An injection from an infinite set $X$ to $\mathbb{N}\implies X$ is countable.

Let $X$ be an infinite set. I've been trying to prove that an injection from $X$ to $\mathbb{N}$ implies that $X$ is countable. I know this boils down to showing that an injection from $X$ to $\mathbb{N}$ implies the existence of a surjection from $X$ to $\mathbb{N}$. Or, equivalently, that a surjection from $\mathbb{N}$ to $X$ implies the existence of an injection from $\mathbb{N}$ to $X$.

Could someone give a proof of one of the above statements?

-
Hint, any infinite subset of $\mathbb N$ is countable. –  Thomas Andrews Sep 7 '12 at 20:08

Let $f:X\to\Bbb N$ be your injection. Let $M=f[X]$. First define a bijection $g:\Bbb N\to M$ recursively as follows. First, $g(0)=\min M$. If $n\in\Bbb Z^+$, and $g(k)$ has been defined for $k<n$, let $$g(n)=\min\Big(M\setminus\{g(0),\dots,g(n-1)\}\Big)\;.$$ It’s straightforward to verify by induction that $g$ is a bijection.

Added: First, it’s clear that $g$ is injective, since the construction ensures that if $m<n$, then $g(n)\ne g(m)$. To show that $g$ is surjective, it suffices to show that for each $n\in\Bbb N$, $$\{g(k):k<n\}=\{m\in M:m<g(n)\}\;:\tag{1}$$ this ensures that each member of $M$ less than $g(n)$ is already ‘hit’ by the function $g$, so $g$ has no ‘holes’ in its range.

$(1)$ is trivially true for $n=0$: both sides are empty. Suppose that it holds for some $n\in\Bbb N$; we want to show that $\{g(k):k\le n\}=\{m\in M:m\le g(n)\}$. It’s clear that $\{g(k):k\le n\}\subseteq\{m\in M:m\le g(n)\}$, so suppose that $m\in M$, $m\le g(n)$, and $m\notin\{g(k):k\le n\}$. Then $m<g(n)$, and $m\notin\{g(k):k<n\}$, contradicting the definition of $g(n)$ as the smallest member of $M$ not in $\{g(k):k<n\}$. $\dashv$

Since $f$ is an injection, it’s a bijection from $X$ to $M$, and $f^{-1}$ is a bijection from $M$ to $X$. We now have

$$\Bbb N\overset{g}\longrightarrow M\overset{f^{-1}}\longrightarrow X\;,$$

where each of the maps is a bijection, so their composition is a bijection from $\Bbb N$ to $X$.

-
"It’s straightforward to verify by induction that $g$ is a bijection." Could you sketch this proof? –  ohmygoodness Sep 10 '12 at 19:53

Let $f : X \to \mathbb{N}$ be an injection.

Being a subset of $\mathbb{N}$, the set $f(X) = \{ f(x)\,:\, x \in X \}$ is well-ordered, and in particular it has a least element, a 2nd-least element, a 3rd-least element, and so on. Define $g : f(X) \to \mathbb{N}$ by sending the $n^{\text{th}}$-least element of $f(X)$ to $n \in \mathbb{N}$. Then the composite $g \circ f : X \to f(X) \to \mathbb{N}$ is in fact bijective, not merely surjective!

Essentially what $g$ does here is it pushes everything downwards so that there are no gaps.

-

An injection from $X$ to $\mathbb{N}$ is a bijection from $X$ to $C \subset \mathbb{N}$. As every subset of $\mathbb{N}$ is countable, we are done.

-
In fact, wikipedia states your problem as the definition. –  Karolis Juodelė Sep 7 '12 at 20:03
I think the author of the question meant by "countable" "equinumerous to $\mathbf N$", so it's not that immediate, especially in the absence of choice. (Not that what's left is particularly complicated, but...) –  tomasz Sep 7 '12 at 20:04
Injection does not imply $|X| = |\mathbb{N}|$ at all, as $X$ could be finite. Though even with the word "infinite" added, my proof is not wrong, is it? –  Karolis Juodelė Sep 7 '12 at 20:32
what about if $f$ is surjection from $X$ to $\mathbb N$ , then $X$ is countable. –  Struggler May 18 at 9:28