# Countability of a Set

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

Suppose that $E$ is countable. Then there is a bijection from $\mathbb{N}$ to $E$ by definition of countability and this implies this direction of the proof.

Now suppose that there exists an onto map $f: \mathbb{N} \to E$. If this function is onto, then let us consider the family $\{f^{-1}(x): x \in E\}$ of subsets of $\mathbb{N}$, where $f^{-1}(x):= f^{-1}(\{x\})$. Because $f$ is onto, $f^{-1}(x) \neq \emptyset \quad \forall x \in E.$ So for each $x\in E$, let us choose an integer $n_x \in \mathbb{N}$ with $f(n_x)=x$.

We now define a map $g: E \to \mathbb{N}$ with assignment $g(x)=n_x$.

Up to this point, I believe that I need to show that $g$ is one-to-one since we are already given a surjection from $\mathbb{N}$ to $E$; this would give us an injection and a surjection, and thus a bijection which will prove this direction.

However, if $g$ is one-to-one, then

$g(x) = g(y) \Rightarrow n_x = n_y$. Does this mean that the same integer $n \in \mathbb{N}$ is selected regardless of the input that depends on $x \in E$?

How can this argument be improved?

• If your definition of countability is a bijection from $\mathbb{N}$ to $E$, then the statement is false. Consider $E=\{a,b\}$. – vadim123 Mar 13 '15 at 20:36
• Sometimes "countable" is used to mean what is more precisely called "countably infinite", which means a bijection with $\mathbb{N}$ exists. How does your source define "countable"? – Ian Mar 13 '15 at 20:56
• The definition of countable which I am working with is that there is a bijection from either $\mathbb{N}$ or from some $\{1,2, \ldots , n \}$ to $E$ where $E$ is a subset of a topological space $(X, \mathscr{T})$. I am not sure if this is relevant, but this definition follows the definition of separable in my notes. – Jamil_V Mar 13 '15 at 22:20
It isn't true that a set $E$ is countable if and only if there is an onto map from $\mathbb{N}$ to $E$, because the empty set is countable, but there is no map at all from $\mathbb{N}$ to the empty set.
Meanwhile, what is true is that a set $E$ is a countable nonempty set just in case there is an onto map from $\mathbb{N}$ to $E$.