Prove that functions map countable sets to countable sets

One of my homework problems asks to prove that if $f:X\to Y$ is a function and $A$ is a countable subset of $X$, then $f(A)$ is countable.

I believe I have a valid proof by partitioning the set A into equivalency classes based in image under $f$. Then using that partition as domain for a choice function $C_f$ back to $A$. So now the function $f$ restricted to the domain (range $C_f$) $f|_{range(C_f)}$ maps to $f(A)$ 1-1 and onto. Therefore

$$|f(A)|=|range(C_f)|\leq |A|=\aleph_0$$ $\therefore f(A)$ is a countable set. $\quad \blacksquare$

My problem is that I used the axiom of countable choice $AC_\omega$ in my proof but that isn't a part of the course I am taking. Does anyone have a simpler proof or one that does not involve Choice?

Solution 1:

You have indeed invoked choice, but not in an essential way.

Remember that by assumption $A$ is countable - so you have a map $g$ from $A$ to $\mathbb{N}$. This gives us a well-ordering of $A$: $$\alpha\prec\beta\iff g(\alpha)<g(\beta).$$ We can use this to explicitly construct a choice function: just pick the "$\prec$-least" element of each equivalence class, and this gives an injection from $B$ to $A$ (take $b$ to the $\prec$-least element which $f$ maps to $b$).