1
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you know that $x < y$ in your first sentence? $\endgroup$ – layman Jul 31 '15 at 17:57
  • $\begingroup$ Because if $x > y$, then $f(x) > f(y)$, which isn't true here since $f(x) = 0$ and $f(y) = 1$. (Yeah I answered my own question. What?) $\endgroup$ – layman Jul 31 '15 at 17:59
  • $\begingroup$ @user46944 exactly! for strictly monotone functions the implication $f(x)<f(y)\Rightarrow x<y$ holds $\endgroup$ – user190080 Jul 31 '15 at 19:47
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that if we modify the requirement on $f$ to be "$a\le b\implies f(a)\le f(b)$," then there are in fact such $f$ - e.g., $f$ sends all negative rationals to $0$, and all nonnegative rational $q$ get sent to $[q]$, the floor of $q$ (the greatest integer $\le q$). $\endgroup$ – Noah Schweber Jul 31 '15 at 18:57
  • $\begingroup$ Actually, this makes me wonder if the question was intended to be about functions from $\mathbb{N}$ to $\mathbb{Q}$ instead, in which case surjectivity is relevant. $\endgroup$ – Noah Schweber Jul 31 '15 at 19:24
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note that editorial comments on the form of the question (e.g. titles being standalone sentences, and not part of the question body) should be given in the comments, not the answers. $\endgroup$ – Asaf Karagila Jul 31 '15 at 18:57
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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