2

For school, I have to prove that every finite subset of $\mathbb N$ is countable. Wikipedia tells me, that "By definition a set $S$ is countable if there exists an injective function $f$ from $S$ to the natural numbers.". I'm probably missing something obvious here, but why is this true?

Srivatsan
  • 26,311
fabian789
  • 171
  • 1
    That means you can tag (or name, or count) each element in $S$ via an element in $\mathbb{N}$. That's actually the definition of counting. Which part exactly makes you uncomfortable in that sentence? –  Oct 08 '11 at 08:41
  • @SrivatsanNarayanan Yes, but I didn't know ho to add the N... – fabian789 Oct 08 '11 at 08:47
  • @percusse mm, so you can say that $s_1$ is Element 1, $s_2$ Element 2? – fabian789 Oct 08 '11 at 08:49
  • 1
    Yes, exactly. If it is a finite element set, you can exhaust its elements by simply assigning elements from $\mathbb{N}$. That's what you are doing when counting anyway. :) Then, of course, there are infinite countable sets (odd numbers set etc.) and uncountable sets. –  Oct 08 '11 at 08:56
  • @percusse OK thanks! I somehow didn't see that you are assigning elements from $\mathbb{N}$, but now it makes sense. Thanks! – fabian789 Oct 08 '11 at 09:06

1 Answers1

2

If it is a set with finite number of elements, you can exhaust its elements by simply assigning elements from $\mathbb{N}$. This is a special case of the definition : A set $S$ is countable if and only if there exists a one-to-one correspondence with a subset of natural numbers.