# Incompleteness of the Rationals

(part of the [coronavirus-in-R course](https://github.com/alexhkurz/coronavirus-in-R/blob/master/README.md) ... [next](https://hackmd.io/@alexhkurz/SJ8Eehu9U))

This lesson can be skipped without loosing track. We cross here the border line that separates high-school maths from university maths and calculus from analysis.

The problem we pose ourselves is the following.

Intuitively, the rational numbers have holes and the reals don't.
Can we make this mathematically precise?

More precisely, we have seen that roots such as $\sqrt 2$ are missing from the rationals $\mathbb Q$ but that there is an algorithm computing them as decimal numbers in $\mathbb R$.

Our aim is to mathematically define what it means for a numberline to be *complete* and then to show that $\mathbb Q$ is not complete while $\mathbb R$ is complete.

The challenge is: Can we say that there are numbers missing from $\mathbb Q$ without already seeing $\mathbb Q$ as a subset of a larger set such as $\mathbb R$? How do we know that something is missing from $\mathbb Q$ without knowing about $\mathbb R$ already?

We first tried to define what a gap is, with the aim to show that $\mathbb Q$ has gaps, but $\mathbb R$ doesn't. I am not saying that this is not possible, but we run into the following difficulty.

$\mathbb Q$ is *dense*, that is, whenever we have $x<y$ then there is a $z$ such that $x<z<y$.

Doesn't that mean that $\mathbb Q$ has no gaps? Nevertheless we know that numbers such as $\sqrt 2$ are missing.

A good starting point to solve this puzzle is the algorithm that computes square roots.

**Notation:** Let $x,y$ be two numbers such that $x\le y$. Then we write $[x,y]$ for the set of all numbers $z$ such that $x\le z\le y$. We call $[x,y]$ an **interval**.

**Remark:** This definition of the interval $[x,y]$ depends on whether we interprete it in $\mathbb Q$ or $\mathbb R$.

**Example:** The algorithm computing $\sqrt{12}$ produces a sequence of nested intervals such as
\begin{align}
[3&,4] \\
[3.4&,3.5] \\
[3.46&,3.47] \\
[3.464&,3.465] \\
[3.4641&,3.4642] \\
[3.46412&,3.46413] \\
[3.4641201&,3.4641202] \\
&\ldots
\end{align}

(The picture I drew on the whiteboard had the intervals getting thinner, not wider.)

This sequence gets closer and closer to $\sqrt{12}$. Even though $\sqrt{12}$ is not in $\mathbb Q$, there is such a sequence of nested intervals in $\mathbb Q$.

We can now see clearly the difference between $\mathbb Q$ and $\mathbb R$:

While a sequence of nested intervals as above exists in both $\mathbb Q$ and $\mathbb R$ there is one important difference:

- If taken in $\mathbb Q$, there is no number that is in all intervals.
- If taken in $\mathbb R$, there is (precisely) one number in all intervals, namely $\sqrt{12}$.

So we can now formulate our aim more clearly:

Define "sequence of nested intervals" in such a way that for all sequences of nested intervals in $\mathbb R$ there is one (and only one) number that is in all intervals.

Here is the definition. (One can spend some time before coming up with this.)

**Definition:** A ***sequence of nested intervals*** is a sequence of intervals
\begin{align}
[x_0&,y_0] \\
[x_1&,y_1] \\
\ldots& \\
[x_n&,y_n] \\
\ldots &
\end{align}

such that
- intervals are nested, that is, for all $n\in\mathbb N$
$$x_n\le x_{n+1}\quad\quad y_{n+1}\le y_n$$
- and intervals get arbitrarily thin, that is, for all $\epsilon>0$ in $\mathbb Q$ there is $n\in\mathbb N$ such that $$y_n-x_n\le\epsilon.$$

**Explanation:** We use $n$ to name intervals. The first bullet point says that the $n$-th interval contains the $(n+1)$-st interval. The second item says that for any width $\epsilon$ there is an interval thinner than $\epsilon$.

**Terminology:** We say that a number is contained in a sequence of nested intervals if it is an element of all the intervals.

With this definition and terminology, we can now say what it means that there are no missing elements:

**Definition:** We say that a numberline is ***complete*** if every sequence of nested intervals contains an element.

With this terminology we can reformulate a result that we proved before:

**Theorem:** $\mathbb Q$ is not complete.

*Proof:* We have shown before that [$\sqrt{2}$ is not rational]() but can be [approximated by a sequence of nested intervals](). QED

The next task is to prove that the real numbers are actually complete.

But before we do this we should learn more about how our definition of completeness works. As a warm-up, in the next lesson we will show that each sequence of nested intervals contains at most one number.