3

Prove that there does not exist a surjective function f: $\mathbb{Q}\rightarrow \mathbb{R} $.

I think a proof by contradiction would work which means we want to prove $$\neg (\forall{y}\in \mathbb{R}, \exists{x}\in\mathbb{Q}, ~f(x) = y)$$ which is equivalent to $$(\exists{y}\in \mathbb{R}, \forall{x}\in\mathbb{Q}, ~f(x) \not= y).$$

My logic is that since the set of rational numbers, $\mathbb{Q}$, is countably infinite and the set of real numbers, $\mathbb{R}$, is uncountably infinite, then we can try to choose one element in $\mathbb{Q}$ at a time to pair with multiple elements in $\mathbb{R}$. However, we'll eventually find some element in $\mathbb{R}$ that has no pre-image in $\mathbb{Q}$.

I'm a bit unsure if my logic is correct and how to write this formally.

Daniel Cazares
  • 715
  • 2
    You have the right idea. The proof essentially follows from the definition of countable and uncountable sets. Cantor's diagonal argument shows that there is not a surjective function between $\mathbb{N}$ and $\mathbb{R}$, and you also know that there is a surjective function between $\mathbb{Q}$ and $\mathbb{N}$, so you essentially need to show that if there were a surjection between $\mathbb{Q}$ and $\mathbb{R}$, then there would have to be one between $\mathbb{N}$ and $\mathbb{R}$, a contradiction. –  Nov 24 '13 at 07:37

1 Answers1

2

Basically the comment of @nsanger but since I was already typing this I'll post it anyway.

This follows directly from Cantor's diagonal argument: a countable sequence cannot contain all real numbers. Here is a slight variation of that idea.

Let $f:\mathbb{N}\to \mathbb{R}$ be any function. Construct a sequence of closed intervals $$\mathbb{R} \supset I_0 \supseteq I_1 \supseteq \ldots $$ such that $f(k) \not \in I_m$ for all $k \leq m$. (You only need to consider one extra function value at each step.) The intersection of all these intervals is not empty but it does not contain any number $f(k)$. Therefore $f$ is not surjective. Now use that $\mathbb{Q}$ is countable to complete this argument.

WimC
  • 32,192
  • 2
  • 48
  • 88
  • Is there any need of considering $I_0$? –  Jun 26 '16 at 15:40
  • Sorry I made a foolish statement before.My confusion lies on the intersection.I don't understand why does the intersection contain no f(k)?Please make me understood this fact clearly. –  Jun 27 '16 at 03:15
  • At last I have understood the fact.The fact is that if there exist any $f(j)$ in the intersection then $f(j)$ € $I_k$ only if $k \leq j-1$ which contradicted the fact that $f(k)$ is in the infinite intersection.But beside it I have also a confusion.@Wimc You have considered a sequence of closed (not bounded) intervals.Is Cantor's intersection theorem valid for only sequence of closed intervals (not bounded)? –  Jun 27 '16 at 03:50
  • If you consider a sequence f : N -> R by f(n) = n, n € N.Then what is $I_k$?Is it not the interval [k+1,infinity]? Then the intersection contains no point.Isn't it? –  Jun 27 '16 at 04:21
  • @A.Chattopadhyay. Yes, intended is a nested sequence of bounded closed intervals. – WimC Jun 27 '16 at 16:56