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

  • 1
    Ok @AllisonCameron . Grea$t$ 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.