# 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.

• Note that Cantor's "diagonal" method usually mean his digit-based proof that $\mathbb R$ is not countable. His enumeration of $\mathbb Q$ or $\mathbb N^2$ is known as the "zig-zag" method. Mar 2, 2017 at 14:04
• @Henning Makholm, thank you for that, I will edit the question to reflect your input. Mar 2, 2017 at 15:22

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).

Yes.

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.)

• Does doing this without the axiom of choice require the well-ordering property, as per Mark's answer?
– Neal
Mar 2, 2017 at 16:06
• Defining a function without using AC doesn't necessarily require well-ordering; you just need to be able to uniquely specify the image of a general element in the domain. In this specific case though, well-ordering gives us an easy way to do this. Mar 2, 2017 at 16:10
• Well yes, that is clear. What I mean is this argument in particular, can it be done generally without AC, say, with two uncountable sets?
– Neal
Mar 2, 2017 at 16:13
• If the domain is well-ordered then yes, it does not matter what the cardinalities of $A$ and $B$ are, this argument holds if we set $g(b)$ to be the smallest element of $f^{-1}[\{b\}]$ say, and we don't need AC for this. Off the top of my head I don't know of other ways of constructing such an injection given the surjection $f$. This answer math.stackexchange.com/a/108814/7090 suggests that there are not too many other ways of doing so. Mar 2, 2017 at 21:51

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.

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$.

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.