1
$\begingroup$

I don't want a proof. I just want verification or correction of the proof I supplied:


We start with the fact that between any two real numbers there is a rational number. There is an infinite amount of real numbers between any two real numbers. Hence any real interval can accommodate the whole set of rational numbers which is also infinite. We know there is a bijection between the set of natural numbers and the set of rational numbers. Hence if there were a "bijection" between the natural and real numbers the domain (the natural numbers) would be mapped entirely within this interval of real numbers to all the rational numbers within. So there cannot be any natural number mapping to something outside of this real number interval so there cannot be a bijection so the set of real numbers is uncountable.

$\endgroup$
  • 3
    $\begingroup$ It is also true that between any two rationals there is another rational. Does your argument then prove that the rationals are uncountable? $\endgroup$ – lulu Feb 9 '16 at 19:42
  • $\begingroup$ @lulu But clearly the rationals cannot fit within an interval of rational numbers. Right? $\endgroup$ – 15yyyyy Feb 9 '16 at 19:44
  • $\begingroup$ Of course they can. I am assuming that you mean "a set of the same cardinality as the rationals". Indeed, just keep taking midpoints. $\endgroup$ – lulu Feb 9 '16 at 19:45
  • $\begingroup$ @15yyyyy : Look at the function $x\mapsto 1/(1+x^2)$. That takes every rational number to a rational number in the interval $(0,1]$. So they do "fit". $\qquad$ $\endgroup$ – Michael Hardy Feb 9 '16 at 19:50
  • $\begingroup$ It is conspicuous that you have not used anything about real numbers that could not be said about the rational numbers. $\endgroup$ – Christian Blatter Feb 9 '16 at 20:37
2
$\begingroup$

"We start with the fact that between any two real numbers there is a rational number."

True. But not just one; there are an infinite number of rational numbers between two real numbers.

"There is an infinite amount of real numbers between any two real numbers."

True. There are an infinite amount of real numbers including an infinite amount of rational numbers between two real numbers.

" Hence any real interval can accommodate the whole set of rational numbers which is also infinite."

Well, it can contain a set of the same cardinality as the whole set of rational numbers. We'll call that "accomodating". (You can't actually put 1/5 into [37.5, 37.8]. But you can put $\phi(1/5)$ into [37.5,37.8] when $\phi$ is a bijection from Q to $Q \cap [37.5,37.8]$.) It can also accommodate the whole set of real numbers between to real numbers. (That is we can make a bijection, $\rho$ where $\rho(x) \in [37.5,37.8]$ for all $x \in \mathbb R$.)

"We know there is a bijection between the set of natural numbers and the set of rational numbers."

True.

" Hence if there were a "bijection" between the natural and real numbers the domain (the natural numbers) would be mapped entirely within this interval of real numbers to all the rational numbers within."

Yes. And what's wrong with that?

Between x and y there are an infinite number of rationals. There is a bijection, $\phi$, between $Q$ and the rationals between x and y. And There is a bijection, $\chi$ between $N$ and $Q$. So $\phi\circ\chi$ is a bijection between $N$ and the rationals between x and y. Nothing wrong with that.

"So there cannot be any natural number mapping to something outside of this real number interval so there cannot be a bijection so the set of real numbers is uncountable. "

Sure there can. That would be just a different mapping. Having one map map to somewhere doesn't "use up" the ability to have another map mapping elsewhere.

Consider $f(n) = 2n + 1$. This is a 1-1 map from the natural numbers to the odd numbers. There is "nothing left" to map to any even number. Yet $g(n) = n$ maps to all the even numbers including the odd numbers. This isn't a contradiction.

======

There is nothing in this proof that pertains to the real numbers that doesn't pertain to the rationals as well. So whatever this proves about the reals it also proves about the rationals. As the rations are countable this can not prove the reals are countable so there must be an error.

The error seems to be that you assume if you have a bijection $\phi: N \rightarrow S$ then you can not also have a bijection $\rho: N \rightarrow T$ where $S$ is a proper subset of $T$.

That is simply not the case on infinite sets. We have bijections from that Natural numbers to the integers, the rationals, the even numbers, etc. many of which are subset and supersets of each other.

In particular we can and do have bijections between the natural numbers and the rationals in any interval.

Let [x,y] be an interval. And let x< q < r < y so that q and r are rational. Let $f(t) = (t/t+1)(1/2(r - q)) + q + (r-q)/2$. $f$ is just such a injection from all rationals to the rationals in [x,y].

$\endgroup$
  • $\begingroup$ I chose your answer because you really did a great job of point out all my errors. Thanks. $\endgroup$ – 15yyyyy Feb 9 '16 at 21:07
1
$\begingroup$

Certainly you can find a mapping from $\mathbb N$ into a specified interval $(a,b)$. And in fact you can find a one-to-one correspondence between $\mathbb N$ and the set $(a,b)\cap\mathbb Q$ of all rational numbers in $(a,b)$. But that doesn't prove you cannot also find a mapping from $\mathbb N$ whose image contains points not in $(a,b)$. For example, the set $\mathbb N$ itself contains points not in $(a,b)$. Therefore this proof does not work.

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