Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
An infinite subset of a countable set is countable
Infinite subset of Denumerable set is denumerable?
Elementary set theory homework proofs

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?

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 1 down vote accepted

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}$?

share|cite|improve this answer
the identity function? just send each number to itself? – user39794 Sep 12 '12 at 3:28
No. What Tarnation wrote is "map each number (element) of T to the natural number matching its index". Some care is required here. – DonAntonio Sep 12 '12 at 3:41
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
@donantonio That's what I meant, I just wasn't saying it clearly. Thanks everyone for all your help! :) – user39794 Sep 12 '12 at 3:50
Ok @AllisonCameron . Great example of why so many times students get low grades in exams: they meant something yet they wrote something meaning anything else. Good it happened to you here and not in class. – DonAntonio Sep 12 '12 at 3:52

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.

share|cite|improve this answer