7

The following exercise in an analysis text and I am trying to solve it without concepts of general topology but fail.

Show that there does not exist a strictly increasing function $f : \mathbb Q \to \mathbb R$ such that $f(\mathbb Q) = \mathbb R$.

Attempt 1. Suppose that the function $f(D) = \mathbb R$ is monotone. If its image $f(D)$ is an interval, then the function $f$ is continuous. So, if we suppose by contradiction that a strictly increasing function $f : \mathbb Q \to \mathbb R$ exists such that $f(\mathbb Q) = \mathbb R$ it must be continuous.

Attempt 2. Since intersection of the set of irrational numbers of the domain is empty so by a convergence of a sequence in the domain $\mathbb Q$ in either case of converging to a rational or irrational number there is nothing to reach a contradiction.

Attempt 3. The function $f$ is injective and it's not surjective so the inverse function is not defined such that I can use theorems about an inverse of a function.

Please help!

  • 4
    You can use the fact the image of a countable set is at most countable. – Hanul Jeon Aug 26 '16 at 08:15
  • @HanulJeon, yes I thought about that by I didn't use it as I don't know its proof! –  Aug 26 '16 at 08:16
  • Its proof is fairly simple if you are familiar with well-ordering. For a function $f:\Bbb{N}\to A$ you can find a right inverse function $g:f[A]\to \Bbb{N}$ explicitly. – Hanul Jeon Aug 26 '16 at 08:20

4 Answers4

12

A strictly increasing function is necessarily injective. If $f(\mathbb{Q})=\mathbb{R}$, then the function is also surjective (by definition). This would imply that there exists a bijection between $\mathbb{Q}$ and $\mathbb{R}$.

EDIT: For the sake of completion, the statement is still true if $f$ is not assumed to be strictly increasing.

To see this, note that there exists a bijection between $\mathbb{N}$ and $\mathbb{Q}$. Therefore, if there were a surjection from $\mathbb{Q}$ to $\mathbb{R}$, there would be one from $\mathbb{N}$ to $\mathbb{R}$. But note that Cantor's argument actually shows that there is no surjection from $\mathbb{N}$ to $\mathbb{R}$. qed.

As a curiosity, note that this argument does not use AC.

Aloizio Macedo
  • 34,292
  • Thanks. But how can I prove that there cannot be a bijection between a countable and an uncountable set? I know it to be true just by intuition! –  Aug 26 '16 at 08:19
  • 3
    @L.G. It is a definition of an uncountable set. – Hanul Jeon Aug 26 '16 at 08:20
  • 2
    @L.G. As Hanul said, it is the definition of an uncountable set. The issue is proving that $\mathbb{R}$ is uncountable, which is standard procedure, and for which there exists a myriad of approaches (a common, introductory one is Cantor's argument). – Aloizio Macedo Aug 26 '16 at 08:22
11

We don't need the fact that $f$ is increasing. Suppose that $f(\Bbb Q)=\Bbb R$, then for any $x\in\Bbb R$ there is a $r_x\in\Bbb Q$ such that $f(r_x)=x$.

Since there are uncountable many $x\in \Bbb R$, the set of all $r_x$ must also be uncountable. However, $\Bbb Q$ is countable, a contradiction.

BigbearZzz
  • 15,084
7

Here is a proof that does not use the uncountability of $\mathbb{R}$. Suppose $f:\mathbb{Q}\to\mathbb{R}$ is strictly increasing, and let $\alpha\in\mathbb{R}$ be any irrational number. Let $A=(-\infty,\alpha)\cap\mathbb{Q}$ and $B=(\alpha,\infty)\cap\mathbb{Q}$. Then every element of $f(A)$ is less than every element of $f(B)$, so $\sup f(A)\leq \inf f(B)$. Moreover, if $x\in A$, then $x+\epsilon\in A$ for sufficiently small rational $\epsilon>0$, so $f(x)<f(x+\epsilon)\leq \sup f(A)$. Similarly, if $x\in B$, then $f(x)>\inf f(B)$. Thus $$f(\mathbb{Q})=f(A)\cup f(B)\subseteq (-\infty,\sup f(A))\cup (\inf f(B),\infty),$$ so any $y\in [\sup f(A),\inf f(B)]$ is not in the image of $f$.

Eric Wofsey
  • 330,363
  • then how to prove that $[\sup f(A),\inf f(B)]$ is not empty? thanks. –  Aug 26 '16 at 11:51
  • 1
    Since every element of $f(A)$ is less than every element of $f(B)$, $\sup f(A)\leq \inf f(B)$. – Eric Wofsey Aug 26 '16 at 17:38
  • Yes! I hadn't notice closedness of the interval. I accept this because of using concepts of real analysis not topology. Thanks a lot for your help. :) –  Aug 26 '16 at 20:24
  • 2
    @L.G. Mine and Aloizio Macedo's answers use only set theory, not topology at all... (I don't have any problem with you accepting this wonderful answer by the way, just want to pint that out.) – BigbearZzz Aug 27 '16 at 14:48
3

I want to give another proof which actually uses the assumptions: Let $x$ be some irrational number and $(x_n)$ a rational monotone increasing sequence converging to $x$. Then $f(x_n)$ is a mononte increasing sequence and bounded (take some rational $y > x$, then $f(x_n)$ is bounded from above by $f(y)$). Hence the sequence $f(x_n)$ converges to $y$ in $\mathbb{R}$. By surjectivity there is some rational $z$ with $f(z) = y$. By assumption $z > x_n$ for all $n$ and thus $z \geq x$. Since $x$ is irrational we have $z > x$. Now there exists a rational number $x'$ with $z > x' > x > x_n$. We obtain $f(x_n) < f(x') < f(z)$, but then $f(x')$ would already be an upper bound of $f(x_n)$ and thus $f(z) = y \leq f(x') < f(z)$ which is a contradiction.