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?

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.

Solution 5:

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.