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?
Why is a set countable if there is a injective function?
2
$\begingroup$
analysis
-
1That 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? – 2011-10-08
-
0@SrivatsanNarayanan Yes, but I didn't know ho to add the N... – 2011-10-08
-
0@percusse mm, so you can say that $s_1$ is Element 1, $s_2$ Element 2? – 2011-10-08
-
1Yes, 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](http://en.wikipedia.org/wiki/Uncountable_set). – 2011-10-08
-
0@percusse OK thanks! I somehow didn't see that you are assigning elements from $\mathbb{N}$, but now it makes sense. Thanks! – 2011-10-08
1 Answers
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.