Show that there exists a bijection from a set that is countable and infinite into natural numbers.

I know that this question is a bit dumb but I can't prove it explicitly. I mean I can't reconcile the following two statements:

  1. Set $A$ is countably infinite, meaning there exists a bijection from $A$ to $N$.
  2. Set $A$ is countable, meaning there exists an injection from $A$ to $N$ and $A$ is infinite.

It looks intuitive but I can't find a clear bijection given (2).


closed as off-topic by Andrés E. Caicedo, Daniel W. Farlow, Leucippus, John B, Tim Raczkowski Feb 26 '16 at 1:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, Daniel W. Farlow, Leucippus, John B, Tim Raczkowski
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is directly by defintion $\endgroup$ – Micael Jul 12 '15 at 3:18
  • $\begingroup$ @bof sorry typo $\endgroup$ – user10024395 Jul 12 '15 at 3:31
  • $\begingroup$ @Micael the definition of countable infinite is 1. Therefore, I don't think it is directly by definition. $\endgroup$ – user10024395 Jul 12 '15 at 3:33

I think you're asking the following:

Suppose $A$ is infinite, and has an injection into $\mathbb{N}$. Show that there is a bijection between $A$ and $\mathbb{N}$.

Here's how to show this:

Let $f: A\rightarrow \mathbb{N}$ be injective, and consider the image of $f$ - this image can be written as $im(f)=\{a_0<a_1<a_2< . . .\}$. Now, the image of $f$ need not be $\mathbb{N}$ itself - for instance, maybe $f$ maps $A$ onto the even numbers. However, this is easily fixed by providing a bijection $b$ between $im(f)$ and $\mathbb{N}$: $a_0\mapsto 0, a_1\mapsto 1, a_2\mapsto 2, . . . $

Then $b\circ f$ is a bijection from $A$ to $\mathbb{N}$.

EDIT: In detail, here's why any infinite subset of $\mathbb{N}$ is in bijection with all of $\mathbb{N}$: fix $A\subseteq\mathbb{N}$ infinite, and consider the following map $$F: A\rightarrow\mathbb{N}: a\mapsto\vert\{n\in A: n\le a\}\vert.$$ So, for instance, if $A=\{1, 3, 7, . . .\}$, then we would have $F(1)=1$, $F(3)=2$, $F(7)=3$. Let $B=\{F(a): a\in A\}$, and note that $F$ provides a bijection between $A$ and $B$; it is enough to show that $B=\mathbb{N}$.

To see this, note that $B$ is downwards closed: given any $n\in B$ and $m<n$, we have $m\in B$. Now $\mathbb{N}$ has the property that its only infinite downwards-closed subsets is the whole of $\mathbb{N}$. This is proved by induction: since $B$ is infinite, we know that for each $m\in B$ there is a $n\in B$ with $n>m$; since $B$ is downwards closed, this means we have $$m\in B\implies m+1\in B.$$ But this means that $B=\mathbb{N}$. (If you phrase induction as "the only inductive subset of $\mathbb{N}$ is $\mathbb{N}$," this is immediate; if you phrase induction as "any property $P$ which holds of 0, such that $P(n)\implies P(n+1)$, holds of all natural numbers," then this follows by considering the property "is in $B$.")

  • $\begingroup$ why are you sure that there won't be duplicate in the set im(f)? I still don't quite understand. From what I see from your construction, I can turn any injection into N into a bijection. Is that true? $\endgroup$ – user10024395 Jul 12 '15 at 5:40
  • $\begingroup$ Since I only have injection into N, I can't be sure that im(f) is the entire N, such that I can have a bijection between im(f) and N, right? What happens if |im(f)| < |N|? Or can there be nothing that is infinite yet smaller than N? If so, how can one prove it? $\endgroup$ – user10024395 Jul 12 '15 at 5:48
  • $\begingroup$ @user136266 see my edit. $\endgroup$ – Noah Schweber Jul 12 '15 at 6:37

Your set is countable and infinite. As your definition says countable infinite means there exist an injection from $A$ to $\mathbb N$. Let write $A$ as $\{a_1,a_2,a_3,...\}$. Suppose under the injective map $a_1\rightarrow n_1$, $a_2\rightarrow n_2,\dots$. Now to get bijection you simply map $n_1$ to $1$ $n_2$ to $2$, $\dots$. Thus we get a bijection from $A$ to $\mathbb N$.


The Schroder--Bernstein theorem constructs a bijection between two sets $A$ and $B$ if there exists injections $$ f: A \to B $$ and $$ g: B \to A. $$ I think this answers your question.

(see my book Proof Patterns for further discussion and the proof of the theorem.)

  • $\begingroup$ While technically true, this answer is far more complicated than necessary: there's no need to invoke SB to show that infinite sets injecting into $\mathbb{N}$ have bijections with $\mathbb{N}$. In particular, the proof of SB does not have a short easy proof, whereas the question the OP asks does. $\endgroup$ – Noah Schweber Jul 12 '15 at 3:44
  • 1
    $\begingroup$ whether or not it is necessary for this problem, it is something that the OP ought to know, and it certainly answers his question. $\endgroup$ – Mark Joshi Jul 12 '15 at 4:51

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