# if $Y$ is a set and there exists a function $f$ from $\mathbb{N}$ to $Y$ then prove that $f(\mathbb{N})$ is at most countable

if $Y$ is a set and there exists a function $f$ from $\mathbb{N}$ to $Y$ then prove that $f(\mathbb{N})$ is at most countable

-
There is a surjection of $\mathbb{N}$ onto $f(\mathbb{N})$. That's equivalent to countability for $f(\mathbb{N})$. – 1015 Mar 19 '13 at 3:47

Given any domain, $f$ applied to the domain has no more elements than the domain because $f$ has only one image for each element in the domain.

-

To see that $\text{range}(f)$ is countable, we need to see that there is an injection $g : \text{range}(f) \to \mathbb{N}$. To do this, for $y \in \text{range}(f)$ we can let $g(y)$ be the least $n \in \mathbb{N}$ such that $f(n) = y$.

The same argument works to get an injection from the range of a function $f$ to the domain of $f$ whenever the domain of $f$ is an ordinal. (If the domain of $f$ is an arbitrary set, the Axiom of Choice may be needed.)

-