Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Hint, any infinite subset of $\mathbb N$ is countable. –  Thomas Andrews Sep 7 '12 at 20:08

3 Answers 3

up vote 5 down vote accepted

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$.

share|improve this answer
    
"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.

share|improve this answer

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.

share|improve this answer
    
In fact, wikipedia states your problem as the definition. –  Karolis Juodelė Sep 7 '12 at 20:03
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.