[Math] Verification of this proof that the set of real numbers is uncountable.

real numbersreal-analysis

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.

Best Answer

"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].

Related Question