# If T is an infinite subset of $\mathbb{N}$ show that there is a 1-1 mapping of T onto $\mathbb{N}$ [duplicate]

Like the title says: If T is an infinite subset of $\mathbb{N}$, show that there is a 1-1 mapping of T onto $\mathbb{N}$.

I get the idea (like for evens and odds) but I don't know how to prove it for ANY infinite subset of the natural numbers. Any advice?

-

## marked as duplicate by William, Aang, Noah Snyder, Martin Sleziak, Nate EldredgeOct 6 '12 at 15:48

One piece of advice: start with the smallest element of $T$. – Kevin Carlson Sep 12 '12 at 3:18
You can see a mapping $f : T \to \mathbb{N}$ as a way of assigning a natural number to each element of $T$, namely $f(t)$. You could for example use the fact that the set $T$ has an order on it, the one provided by $\mathbb{N}$. – Bogdan Sep 12 '12 at 3:19
So could I say that the smallest element of T maps to 1, the next smallest maps to 2, the next smallest to 3, and so on? – user39794 Sep 12 '12 at 3:20
@William: That one’s a little more general, but it can certainly be adapted to this setting. I didn’t want to point to it, however, because it has a complete answer, and this question is homework. – Brian M. Scott Sep 12 '12 at 3:20
So how do I formalize all this? I was going to write: Let T be any infinite subset of $\mathbb{N}$. Since T is a subset of $\mathbb{N}$, T is ordered. Choose the smallest element of T and send it to 1, the next smallest element of T and send it to 2, etc. Maybe it was less complicated than I thought! Thanks! :) – user39794 Sep 12 '12 at 3:23

If $T \subset \mathbb{N}$ is infinite, we can enumerate the elements of $T$ by $T=\{a_1,a_2,a_3,... \}$, where $i<j \Rightarrow a_i<a_j$. Can you see a natural function we can use to map onto $\mathbb{N}$?
What Don said. If we use the map $f(a_i)=i$, we get a bijective map with the positive natural numbers. – Tarnation Sep 12 '12 at 3:42
It’s a little easier, I think, to define a bijection $f$ from $\Bbb N$ onto $T$ and use its inverse. Define it recursively: $f(0)=\min T$, and if $f(k)$ has been defined for all $k<n$, let $$f(n)=\min\Big(T\setminus\{f(k):k<n\}\Big)\;.$$ If you think a bit about what this construction is doing, you should be able to see that it must be yield a bijection, though you may still struggle a bit to write down a proof. Since the construction is recursive, try a proof by induction that the resulting function is onto.