I tried to prove this statement for a non-empty set $A$
$$A ~~\text{finite or countably infinite} ~\Leftrightarrow~ \exists\varphi : \mathbb{N} \rightarrow A ~~\text{surj}.$$
The $\Rightarrow$ is pretty straight forward and does not involve my question, so I will only go over what I came up with for the other direction.
Proof (by contradiction) We know that there exists a surjection $\varphi : \mathbb{N} \rightarrow A$ . So for every $a \in A$ the set $\varphi^{-1} (a)$ is non-empty. Since, by assumption, $A$ is not finite, the axiom of choice is needed to choose one element out of every $\varphi^{-1} (a)$ . Collecting those and putting them into $N \subset \mathbb{N}$ , $\varphi$ induces a bijection $N \rightarrow A$ which contradicts $A$ not being countably infinite (or finite).
Now I have 3 questions (aside from is the proof correct?)
- Is the usage of the axiom of choice correct?
- Is the axiom needed to get one element out of every $\varphi^{-1} (a)$ ?
- Is there a proof of this statment that does not rely on the axiom of choice?
No choice is needed here.
The reason is that the natural numbers are well ordered. So every surjection from the natural numbers can be split: choose the least integer from each fiber.
Finally, by enumerating a set of natural numbers we get that every subset of the natural numbers is finite or countable. And so the result follows.