Let X be an enumerable set and let Y be any set. If there is a surjective function f : X → Y, how do I prove that Y is countable?
I know a set is enumerable if there's a bijection $Z^+$ → X, so that it
is equipotent to $Z^+$. I also know that a set is countable if it is finite or denumerable, I'm just not sure how to tie that all together?
Best Answer
We generate subset $X'$ by enumerating $X$, and mapping $f$ on each element $x$. If we have already seen $f(x)$ previously in the enumeration, we discard $x$.
Since we discarded only duplicate results, we have a subset $X' \subseteq X$ such that $X'$ is still surjective.
However no two elements of $X'$ map to the same element in $Y$, so it's also injective. Therefore $f$ is a bijective mapping from $X'$ to $Y$.
Since $X$ is countable, $X' \subseteq X$ is as well, therefore $Y$ must be as well.