2
$\begingroup$

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?

  • 1
    One piece of advice: start with the smallest element of $T$.2012-09-12
  • 1
    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}$.2012-09-12
  • 0
    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?2012-09-12
  • 0
    @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.2012-09-12
  • 0
    It’s a little easier (in my opinion) to define the map in the other direction, but the basic idea is sound.2012-09-12
  • 1
    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! :)2012-09-12

2 Answers 2

1

If $T \subset \mathbb{N}$ is infinite, we can enumerate the elements of $T$ by $T=\{a_1,a_2,a_3,... \}$, where $i. Can you see a natural function we can use to map onto $\mathbb{N}$?

  • 0
    the identity function? just send each number to itself?2012-09-12
  • 0
    No. What Tarnation wrote is "map each number (element) of T to the natural number matching its *index*". Some care is required here.2012-09-12
  • 0
    What Don said. If we use the map $f(a_i)=i$, we get a bijective map with the positive natural numbers.2012-09-12
  • 0
    @donantonio That's what I meant, I just wasn't saying it clearly. Thanks everyone for all your help! :)2012-09-12
  • 1
    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.2012-09-12
2

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, let $$f(n)=\min\Big(T\setminus\{f(k):k 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.