Hi everyone I'd like to know if the following reasoning is correct, any suggestion would be great. Thanks.
Proposition: Let $Y$ be a set and let $f: \mathbb{N}\rightarrow Y$ be a function. Then $f[\mathbb{N}]$ is at most countable.
Proof: If $Y$ is finite the result follows, this is because$f[\mathbb{N}]\subset Y$ and any subset of a finite set is finite and has at most the size of the set in which is contained.
We may assume that the set $Y$ is infinite. We set $A:= \{\,n\in\mathbb{N}:f(i)\not=f(n) \,\,\text{ for any }i< n\, \}$. And we define the function $g:A \rightarrow f[\mathbb{N}]$ as the restriction of $f$ in $A$. We claim that the function $g$ is a bijective map. From the definition of $A$ we already know that the map is $1:1$. We will show that also is onto.
Let $y\in f[\mathbb{N}]$. Suppose for the sake of contradiction that there is no $n\in A$ such that $g(n)=y$. Since $y$ lies in the image of $f$, then there is some $j\in \mathbb{N}$ for which $y=f(j)$. Then either $f(j)\not= f(i)$ for any $i<j$ or there exists some $i<j$ such that $f(j)= f(i)$. For the former, $j$ lies in $A$ (by its definition). For the latter, the set $\{\, n\in \mathbb{N}: f(j)=f(n)\, \text{and }\,n\not=j \}$ is non empty, and hence has a minimum element. Let $m$ be its minimum element. Then $f(m)\not=f(n)$ for any $n<m$ and thus $\,m\in A$ but $g(m)=f(m)= f(j)=y$. Thus any case leads to a contradiction. The result follows by reductio ad absurdum. Hence $f$ is surjective and injective, i.e., a bijective map.
Since there is a bijection between $A$ and the images of the natural numbers under $f$, both have the same cardinality. Also we already know that $A\subset \mathbb{N}$ and any set of the natural numbers is denumerable, thus $f[\mathbb{N}]$ is countable. $\Box$
