# Does this proof need the axiom of choice?

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?

## 1 Answer

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.