Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
1  
Looks good, can simplify with en.wikipedia.org/wiki/…;. –  vadim123 Dec 18 '13 at 4:06
    
Thanks in other source I saw the Cantor-Bernstein theorem. :) –  Jose Antonio Dec 18 '13 at 4:21

1 Answer 1

up vote 1 down vote accepted

Yes, it's correct. Nice proof!

share|improve this answer
    
Thanks is really comforting to know that my proof is correct. :) –  Jose Antonio Dec 18 '13 at 4:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.