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?

Many thanks in advance for your time and assistance.

  • 3
    $\begingroup$ If your definition of countability is a bijection from $\mathbb{N}$ to $E$, then the statement is false. Consider $E=\{a,b\}$. $\endgroup$ – vadim123 Mar 13 '15 at 20:36
  • $\begingroup$ 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"? $\endgroup$ – Ian Mar 13 '15 at 20:56
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ Ok, so how would one prove the latter statement? $\endgroup$ – Jamil_V Mar 13 '15 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.