# Why Are the Reals Uncountable?

Let us start by clarifying this a bit. I am aware of some proofs that irrationals/reals are uncountable. My issue comes by way of some properties of the reals. These issues can be summed up by the combination of the following questions:

• Is it true that between any two rationals one may find at least one irrational?
• Is it true that between any two irrationals one may find at least one rational?
• Why are the reals uncountable?

I've been talking with a friend about why the answer of these three questions can be the case when they somewhat seem to contradict each other. I seek clarification on the subject. Herein lies a summary of the discussion:

Person A: By way of Cantor Diagonalization it can be shown that the reals are uncountable.

Person B: But is it not also the case that one may find at least one rational between any two irrationals and vice versa?

Person A: That seems logical, I can't pose a counterexample... but why does that matter?

Person B: Wouldn't that imply that for every irrational there is a corresponding rational? And from this the Reals would be equivalent to 2 elements for every element of the rationals?

Person A: That implies that the Reals are countable, but we have already shown that they weren't... where is the hole in our reasoning?

And so I pose it to you... where is the hole in our reasoning?

-
I am just posting this here with the awareness that I might be totally wrong, but all rationals (which are obviously countable) eventually "cycle". Now rationals cycle after a finite number of integers. As an example, 3/7=0.428571428571... But between any two rationals of cycle length N, there are infinitely many irrational number which could have a pseudo-cycle of length N till a certain time and then have totally new digits after that. Though this is not the same as cantors proof, the idea is that for every two rationals, one can produce infinitely many irrationals. –  picakhu Jan 25 '11 at 22:33

## 8 Answers

The problem is here: "Wouldn't that imply that for every irrational there is a corresponding rational? And from this the Reals would be equivalent to 2 elements for every element of the rationals?" The problem is that for many different pairs of irrationals you would be choosing the same rational in between. If you want to avoid this problem, you'd have to describe a procedure by means of which:

1. You uniquely specify for each pair of irrationals $a<b$ a rational $c$ in between. (This is easy but non-trivial since there are infinitely many candidates for $c$.)

2. Different pairs get assigned different rationals.

Of course, task 2 is impossible, so there is no correspondence between irrationals and rationals.

-
Or, in other words, the map the OP constructed is neither injective nor surjective. –  Willie Wong Jan 25 '11 at 20:08
@Willie: Well, "constructed" seems rather strong... –  Arturo Magidin Jan 25 '11 at 20:29
You explain the fact with the fact. Why is task 2 impossible? (The original question seems to assume we have not yet fully accepted that there is this difference between reals and rationals) –  Raphael Jan 26 '11 at 12:37
@Raphael: If I understand the question correctly, akdom thought that this construction was a counterexample to the uncountability of the reals. It would only be a counterexample if this map was injective, which it is not (as witnessed by the usual Cantor construction). So there is no need to explicitly falsify the injectivity by a different argument. –  Bertram Jan 28 '11 at 9:33

What you can conclude (although there are other means) is that there are uncountably many sets of rational numbers. If $a\lt b$ and $c\lt d$ are distinct pairs of irrational numbers, then the set of rational numbers in the interval $(a,b)$ is distinct from the set of rational numbers in $(c,d)$. For example, if $b\lt d$, then there is a rational number $r$ in the interval $(\max(b,c),d)$, and thus $r$ is in $(c,d)$ but not $(a,b)$. To make this more concrete, the sets of rational numbers in the intervals $(0,b)$ are distinct as $b$ ranges over the positive irrational (or real) numbers.

I'll note that this is quite a roundabout way to prove this, because proving that the set of real numbers is uncountable is no more basic than proving that in fact the set of subsets of any countable set is uncountable, but it strikes me as the closest positive result to what you were looking for.

-

Your reasoning shows that there is a mapping from ordered pairs of irrationals to the rationals, and a mapping from ordered pairs of rationals to the irrationals. Neither of these maps has any other special properties; in particular, the first is not one-to-one (many pairs of irrationals must map to the same rational), and the second is not onto (many irrationals are not mapped to by any ordered pair of rationals). Both the rationals and the irrationals are dense in the reals, which is what explains your observations; but this does not imply that there is a bijection between them.

-

In fact, between any two distinct irrational numbers $a$ and $b$, there are countably infinitely many rational numbers.

Proof: Without loss of generality, suppose $0 < a < b < 1$. Each has an infinite decimal expansion: $$a = \sum_{i = 1}^{\infty} a_i 10^{-i} \mbox{ and } b = \sum_{i = 1}^{\infty} b_i 10^{-i}$$ Note that for $b$ to be irrational, infinitely many $b_i$ must be non-zero. Because $a \neq b$, there is some least value of $i$ such that $a_i \neq b_i$ (i.e. there is a first decimal place at which $a$ and $b$ disagree); let that value be $N$. Then $a_N < b_N$.

Now let $c_n$ be a rational number defined as $$c_n = \sum_{i = 1}^{n} b_i 10^{-i}$$ where $n > N$. The decimal places of $c_n$ agree with each of the decimal places of $b$ up to and including $b_N$, therefore the decimal places of $c_n$ agree with the decimal places of $a$ up to, but not including $a_N$. So the $N$th decimal place is the first place where $c_n$ and $a$ disagree, and $c_n$'s $N$the decimal place is greater than $a$'s $N$th decimal place, therefore $c_n > a$.

Yet because the decimal expansion of $c_n$ terminates while the decimal expansion of $b$ does not, $c_n < b$. So $a < c_n < b$, i.e. $c_n$ is a rational number in between $a$ and $b$. There are at least as many distinct $c_n$ as there are $n > N$ such that $b_n \neq 0$, i.e. countably infinitely many, which proves the claim.

Moral: Infinity is stranger than you think.

-

Yes, between any two irrationals there is always (at least one) rational: let $r$ and $s$ be irrationals, say $r\lt s$. For simplicity we may assume they are both positive (if $r\lt 0$ and $s\gt 0$, then we can take $0$ as a rational between them; if $r\lt s\lt 0$, we can do what I'm about to do to find a rational $q$ with $-s\lt q\lt -r$, and then $-q$ will lie between $r$ and $s$ and be rational).

Let $n$ be an integer such that $0\lt \frac{1}{n}\lt \frac{r-s}{2}$; we know that $S=\{m\in\mathbb{N}\mid \frac{m}{n}\gt r\}$ is nonempty by the Archimedean property. Being a nonempty set of natural numbers, it has a least element; call it $M$. Then $r\lt \frac{M}{n}$. If $s\lt \frac{M}{n}$, then $$\frac{M-1}{n} = \frac{M}{n}-\frac{1}{n} \geq \frac{M}{n}-\frac{r-s}{2} \gt s-\frac{r-s}{2} = \frac{s+r}{2} \gt \frac{r+r}{2} = r.$$ contradicting that $M$ is the smallest positive integer such that $\frac{M}{n}\gt r$ (notice that we cannot have $M-1=0$, because that would mean $M=1$, so $\frac{1}{n}\gt r \gt \frac{r-s}{2}$).

This means that $\frac{M}{n}\leq s$; and since $\frac{M}{n}$ is rational and $s$ irrational, then $\frac{M}{n}\lt s$. Therefore, $r\lt \frac{M}{n}\lt s$, so there is at least one rational between $r$ and $s$.

Yes, between any two rationals there is always at least one irrational. You can proceed along similar lines: given any positive integer $n$, there is always an irrational $x$ with $0\lt x\lt \frac{1}{n}$. To see this, just take $x=\frac{\sqrt{2}}{2n}$. Then $x\lt\frac{1}{n}$ if and only if $\frac{\sqrt{2}}{2}\lt 1$, which is true. So there is at least one such irrational.

Now let $r$ and $s$ be two rationals, with $r\lt s$. Let $x$ be an irrational with $0\lt x \lt \frac{s-r}{2}$. Now take $x+r$; this is irrational (if $x+r$ were rational, then so would $(x+r)-r = x$, a contradiction). It is greater than $r$, because $x\gt 0$. And $$r \lt r+x \lt r+\frac{s-r}{2} = \frac{s+r}{2} \lt \frac{s+s}{2} = s,$$ so $r\lt y \lt s$ with $y=r+x$ an irrational.

But no, this does not mean that "for every irrational there is a rational"; for the reasons others have so well explained.

-

Although I'm aware that pointwise limits can do all kinds of freaky stuff, I like to think of how rare the rationals actually are with respect to the reals by analogy of how rare the naturals are (I think I saw this or something similar in the nice introductory book to Analysis I by Harro Heuser):

Consider the family of functions $f_{n,k}(x) = \cos^{2n}(k! \pi x)$.

Since $q$ is a rational number iff there is a $k$ such that $k!q \in \mathbb Z$, we get

$$\lim_{k \to \infty} \, \lim_{n \to \infty} \, f_{n,k}(x) = \chi_{\mathbb Q}(x)$$

So in some sense, the mental picture of two rationals being separated by irrationals in a similar way as the naturals are by nonnaturals is not completely wrong. At least in certain situations (like why the irrationals are a Baire space, whereas the rationals are not) this might help one get a more intuitive understanding, I think.

-
I don't think so: For example if x is irrational the k-limit would then not even be defined, I guess? –  Sam Jan 26 '11 at 19:45

You're applying intuitive logic that works for finite sets to infinite sets.

To complete your proof, you would need to construct 'consecutive' pairs of irrationals, which is not possible.

-

Reals (particularly irrational numbers) are uncountable simply because there is no limit to the creation of new irrational numbers between any two given irrational numbers. So any attempt to denumerate the real numbers (particularly irrational numbers) can be failed by creating a new irrational number out of it! When you think you have denumerated all the real numbers by establishing a biunique correspondence, Cantor's diagonal would break your illusion!

-
Yes, the real numbers are uncountable, but your answer is circular. It does not explain why, it says that they are because the Cantor diagonal argument works, and it works because they are uncountable. –  Asaf Karagila Sep 25 '12 at 17:12