Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $f: \mathbb{Q} \rightarrow \mathbb{N}$ be such that for $x<y$ in $\mathbb{Q}$ one has $f(x) < f(y)$ in $\mathbb{N}$. Prove that $f$ is not surjective.
I tried a proof by contradiction, but I don't know how to proceed it using the theorems of enumerability and Peano Axioms I have.
Assume the your function $f$ would be surjective, so we hit the whole $\mathbb{N}$, that means especially for some $x,y\in\mathbb{Q}$ with $x<y$ we have $$ f(x)=0 \text{ and } f(y)=1 $$ now we choose $z:=\frac{x+y}2$ for which holds $x<z<y,f(z)\in\mathbb{N}$ , so for this it must hold since we have an increasing function $f$ $$ f(x)<f(z)<f(y)\Leftrightarrow 0<f(z)<1 $$ which is a contradiction, since there is no natural number which lies between $0$ and $1$, therefore the function can not be surjective.
I don't really see what surjectivity has to do with this: there is no map $f$ from $\mathbb{Q}$ to $\mathbb{N}$ satisfying $m<n\implies f(m)<f(n)$, at all.
Suppose there were. Then $f(0)> f(-1)> f(-2)>. . .$. But this yields an infinite descending chain of natural numbers, which can't happen.
Note that restricting to positive rationals doesn't help: take $f(1)>f({1\over 2})>f({1\over 3})>. . .$.
Basically the same argument, but phrased differently: there are only finitely many natural numbers between $f(0)$ and $f(1)$, but infinitely many rationals between $0$ and $1$. For $f$ to preserve ordering, $f$ would have to map an infinite set into a finite set.
The current title makes no sense. The previous title was much better. What you really meant was this: "If $f:\Bbb Q\to\Bbb N$ is such that $x<y$ implies $f(x)<f(y)$ show $f$ is not surjective."
Also note that the question should be in the body of the post, not just the title.
Anyway, there is no such function to begin with, surjective or not. Suppose $f:\Bbb Q\to\Bbb N$ is such that $x<y$ implies $f(x)<f(y)$. Choose an integer $N$ so that $$N>f(1)-f(0).$$ Now $f(1/N)>f(0)$, and since the values are integers, $f(1/N)\ge f(0)+1$. Similarly $f(2/N)\ge f(1/N)+1\ge f(0)+2$. And so on; you finally get $$f(1)=f(N/N)\ge f(0)+N.$$So $N\le f(1)-f(0)$, contradiction.
Suppose $f(0)=m$ and $f(1)=n$, so $k=n-m+1 \ge 2$ is an integer. What values could you assign for the following? $$f\bigl(\frac{1}{k}\bigr) \quad, \quad f\bigl(\frac{2}{k}\bigr) \quad, \quad \ldots\quad , \quad f(\frac{k-1}{k})=f(\frac{n-m}{k}) $$ Those are supposed to be $n-m$ different integers between $m$ and $n$. But the number of integers between $m$ and $n$ is only $n-m-1$.
