We have all seen how Cantor showed that the rational numbers are countable with his zig-zag method, but I want to show the same thing without the zig-zag, so here is my approach, does it work?
We can list ALL the rational numbers.
$\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots $
$\frac{2}{1}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \dots $
$\frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \dots $
$\frac{4}{1}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \dots $
$\dots$
Then we will pair the first row with some unique natural numbers. We will take the first prime number two and append fours to it.
$24, 244, 2444, 2444, \dots$
Then the next row will use the next prime number three.
$34, 344, 3444, 3444, \dots$
Then the next row will use the the next prime number five.
$54, 544, 5444, 5444, \dots$
Then the next row will use the the next prime number seven.
$74, 744, 7444, 7444, \dots$
And so on.
Every rational number will be assigned at least one unique natural number, so we know that the cardinality of the rational numbers can't be greater than the cardinality of the natural numbers.
Best Answer
Yes, a surjection $f: \mathbb{N} \rightarrow S$ is enough to show that $S$ is countable. From such $f$ we can easily construct an bijective function, as follows: Let $M \subseteq \mathbb{N}$ be the set of $m \in \mathbb{N}$ for which there exists no $n < m$ with $f(n) = f(m)$. Then $f$ restricted to $M$ is a bijection. Now $M$ is either finite, or infinite. Using the fact that $M$ is well-ordered (it has a smallest element, a second-smallest, etc.) we can construct a bijection between $M$ and the set $\{1,2,\ldots,n\}$ for some $n$ (if $M$ is finite), or $\mathbb{N}$ (if $M$ is infinite).