Is a surjection from the natural numbers enough to show that a set is countable? 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.
 A: 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).
A: Yes.
A more general answer:
Let $A$ and $B$ be arbitrary sets (not necessarily well-ordered).
If $f\colon A \rightarrow B$ is a surjection then by the axiom of choice we can construct an injection $g\colon B \rightarrow A$ by setting $g(b) = a$ where $a\in f^{-1}[\{b\}]$ for every $b \in B$.
So the cardinality of $B$ is at most the cardinality of $A$.
For your specific question set $A = \mathbb{N}, B = S$.
(I'm aware this answer is likely a little OP for the current question, though perhaps it is also useful to see how things can be done in more general settings.)
A: Let $\Bbb N = \{0,1,2,3,\dots \}$.
If $\mathcal P$ be a partition of $\Bbb N$ we have the familiar 'representative to coset/block' surjective mapping from $\Bbb N$ onto $\mathcal P$,
$\quad\quad\quad\quad\quad\quad\quad k \mapsto [n]$
We also adopt the convention here the existence of a set $\text{!}$ with $\Bbb N \cap \text{!} = \emptyset$ and definitions
$\quad \text{min}(\emptyset) = \text{!}$
and
$\quad [\text{!}] = \text{!}\,$
Using recursion we define another function $\Sigma$ from $\Bbb N$ to $\mathcal P \cup \{\text{!}\}$ as follows:
$\tag 1 \Sigma(0) = [0]$
$\text{With } \Sigma(k) \text{ defined for } k \lt n \text{ define}$
$\tag 2  \displaystyle{\LARGE{\Sigma(n) = } \LARGE{[} \; \LARGE{\text{min}(} \, \Bbb N \setminus \bigcup_{k \lt n} \Sigma(k) \, \LARGE{)} \; \LARGE{]}}$
It is easy to check that $\text{!}$ is in the range of $\Sigma$ if and only if $\mathcal P$ is a finite set and that otherwise $\Sigma$ is a bijective correspondence between $\Bbb N$ and $\mathcal P$.
Let $f: \mathbb{N} \rightarrow S$ be a surjective function. Then $f$ can be factored onto its quotient and so by the above $S$ must be a countable set.
A: There are two common definitions of countability. One is more properly called "countably infinite" where $X$ is countably infinite if it can be put in bijection with $\mathbb{N}$. The other, weaker definition of countability is exactly what you said, i.e. that we can map $\mathbb{N}$ onto $X$. So the latter would encompass the former, i.e. a countably infinite set trivially can have $\mathbb{N}$ onto it. But it also holds for finite sets. A set is countably infinite if and only if it's countable and not finite. In a fairly intuitive way, if $f : \mathbb{N} \to X$ is a surjection, and $X$ is infinite, then we can construct a bijection $g : \mathbb{N} \to X$ "induced by" $f$.
A: We can get the result quickly if we already know that
$\quad$ An infinite subset of a countable set is countable
Let $f: \Bbb N \to S$ be a surjection.
The mapping
$\quad s \mapsto \text{min}(f^{-1}(s))$
is an injection of $S$ into $\Bbb N$, so $S$ is countable.
