E is countable $\longleftrightarrow$ there exist a surjection from $\mathbb{N}$ to E

Question

The book I am using for my Introduction of Topology course is Principles of Topology by Fred H. Croom.

I was given the following problem:

Prove that a set $E$ is countable if and only if there is a surjection from $\mathbb{N}$ to $E$.

I have a rough idea on how to prove this. Though the converse is tricky and I am having a hard time coming up with a proof to justify my claim.

$P \rightarrow Q$: Let $E$ be a nonempty countable set. By definition of a countable set, this implies there is a bijection between $\mathbb{N}$ and $E$. Therefore there is a surjection from $\mathbb{N}$ to $E$.

$Q \rightarrow P$: Let there be a surjection from $\mathbb{N}$ to $E$. Thus we have a function $f$ such that $f(\mathbb{N})=E$. Seeking to prove $E$ is countable, we have two cases: if $E$ is finite or if $E$ is infinite.

This is where I am stuck. How would I take the two cases of a finite or infinite $E$? Would I need to find (create) such a function $f$ that makes the bijection from $E$ to $\mathbb{N}$, making $E$ countable? Am I on the right track? Any suggestions?

---

Sorry for the rather long question. If is it rather confusing, let me know so I can clarify. I sincerely thank you for taking the time to read this question. I greatly appreciate any assistance you may provide.

As a disclaimer, I put the General-Topology tag because this question was given in a topology course.

Answer 1

Your definition of "countable" is inconsistent - does "countable" mean "bijectable with $\mathbb{N}$" or "maps injectively into $\mathbb{N}$" - that is, is a finite set countable?

(Let's say we're treating finite sets as countable - this is certainly the definition I'm used to, although I've seen the other used.)

Then I claim we don't need to split into cases to prove $Q\implies P$. Suppose we have a surjection $f: \mathbb{N}\rightarrow E$. I want to build an injection of $E$ into $\mathbb{N}$.

So, given $e\in E$, I need to pick some $n\in\mathbb{N}$ to match up with $e$. My naive idea is to set $n=f^{-1}(e)$, but since $f$ might not be an injection, $f^{-1}(e)$ might not be meaningful: $e$ might have more than one preimage.

Still, if only there were a way of picking a specific element of $A_e=\{m: f(m)=e\}$ . . . If all I know about $A_e$ is that it's a nonempty set of natural numbers, is there a "most efficient" element of $A_e$ I can pick?

Answer 2

Your work is good so far. But you have to actually construct the map.

For each $e \in E$, consider the smallest $n$ that maps to $e$. (This always exists because $f$ is surjective and the naturals are well-ordered.) Define $g: E \to \Bbb{N}$ by $$ g(e) = \min \{ n \in \Bbb{Z} \mid f(n) = e \} $$ I claim that this map is injective. Even if $E$ is infinite, then it may not be surjective, though.

From $g$ you can define a new map that is a bijection. How? Think about how $E$ naturally inherits a total ordering from $\Bbb{N}$ via $f$.

Answer 3

Start with the contradiction. Suppose $E$ is not countable. If $f : N\to E $ is a surjection, there is a subset $A$ in $\mathbb{N}$ such that $f(A)=E$. Now such a set $A$ can not be uncountable since it is a subset of $\mathbb{N}$ therefore $ A$ is countable and so is $E$.