Constructing the Real Numbers (1)
Contents
In a previous pair of posts (Part One and Part Two) I gave a construction of the rational numbers $\Q$ using integers $\Z$ as the starting point. The process went something like this:
- We determined the type of gaps in the integer number line that we wanted to fill in.
- We figured out a way to fill in those gaps by constructing "fractions" out of pairs of integers.
- We realized that many fractions actually gave the same rational number (i.e., they had the same canonical form) so we collapsed all such fractions into their equivalence classes under an intuitive equivalence relation. The set of all such equivalence classes is what we called the "rational numbers".
- We went on to prove that the resulting rational numbers had all the properties that we expected and extended the integers in a natural way.
We are going to follow a similar procedure now and attempt to construct the real numbers $\R$ using the rational numbers $\Q$ as a starting point. This is a bit more challenging, due to the more subtle nature of the gaps between rational numbers, and so it requires some more complex machinery that I will develop in this post. In the next post I will give an actual construction. In the post after that I will give a different but equivalent construction.
Finding a Gap
Gaps? What gaps?! We ensured in our construction of the rational numbers that every two rational numbers have another rational number between them! For instance, the average of any two rational numbers is a rational number that sits between them. We can continue finding rational numbers that are closer and closer together, ad infinitum. So how on earth could there be any gaps?
Well here's one:
If we were to lay a square of side length $1$ on its side as above, so that the square's diagonal coincided with the rational line, we would find that there is in fact no rational number located at the rightmost corner of the square (the red point). Why? Because the length of the diagonal should be $\sqrt{2}$, but this is not a rational number! Thus, we have found a gap. If we want all constructible lengths to correspond to numbers, then the only solution is to add more numbers.
Some mathematicians draw the line here (no pun intended) and take issue with the concept of real numbers. Rational geometry and rational trigonometry (in which quadrance, the square of the length, is considered more fundamental than length itself), offer a way to do most every day calculations using only rational numbers. However, this only serves to push the problem slightly further down the road, since for instance the circumference of a unit circle still cannot be described in this manner. However, most mathematicians, myself included, choose the approach of adding more numbers to fill in such gaps. After all, I find it rather desirable to have real numbers to work with, since they have nice properties and it is useful to have things like calculus at our disposal.
I feel compelled to justify the above example a bit more. After all, I have not proven that the length of the diagonal is $\sqrt{2}$, nor have I proven that there is no rational number whose square is $2$. The first point is a consequence of the Pythagorean Theorem, which I will now prove visually:
Pythagorean Theorem. For any right triangle with leg lengths $a$ and $b$ and hypotenuse length $c$, we have that $c^2 = a^2 + b^2$.
Proof. We give a visual proof. Consider an arbitrary right triangle, as below.
If we draw a square of side length $c$ and line up one side with the hypotenuse of our triangle, we obtain the following picture.
The area of this new square of side length $c$ is certainly $c^2$. However, we see that this area is also the sum of the areas of four copies of the original triangle in pink (taking for granted the invariance of area under rigid transformations) plus the area of the inner green square. The area of each of these four pink triangles is of course $\frac{ab}{2}$. The side lengths of the green square are $\abs{a-b}$, and so the area of this square is $(a-b)^2$. Thus,
$$\begin{align}
c^2 &= 4\left(\frac{ab}{2}\right) + (a-b)^2 \\[.2em]
&= 2ab + a^2 - 2ab + b^2 \\[1em]
&= a^2 + b^2,
\end{align}$$as desired.
Using the Pythagorean Theorem, we see that if the side lengths are $a=b=1$, then it must be that $c^2=2$. Why then are we so sure that $c$ cannot be a rational number? There is a famous proof that tells us that this must be so. First, we will need the following lemma.
Lemma. If $x$ is an integer and $x^2$ is even then $x$ is even.
Proof. We give a proof by contraposition. Suppose that $x$ is odd. Then $x=2n+1$ for some integer $n$. It follows then that
$$\begin{align}
x^2 &= (2n+1)^2 \\[1em]
&= 4n^2 + 4n + 1 \\[1em]
&= 2(2n^2 + 2n) + 1 \\[1em]
&= 2m + 1,
\end{align}$$where $m=2n^2+2n$ is an integer. It follows that $x^2$ is odd. Thus the contrapositive is also true — if $x^2$ is even then so is $x$.
Now for the main event: the proof that $\sqrt{2}$ is not a rational number.
Theorem. There is no rational number $c$ for which $c^2=2$.
Proof. We proceed by contradiction, supposing that there does exist some rational number $c$ for which $c^2=2$. Since $c\in\Q$, there exist integers $p$ and $q$ with $q\ne 0$ and $c=\frac{p}{q}$. We may suppose without loss of generality that $\frac{p}{q}$ is in canonical form, because otherwise we can simply divide numerator and denominator by their greatest common divisor to obtain a new fraction that is in canonical form, as I showed in my second post on the construction of the rational numbers.
Now since $c^2=2$ and $c=\frac{p}{q}$, of course it follows that
$$\begin{align}
2 &= c^2 \\[.8em]
&= \left(\frac{p}{q}\right)^2 \\
&= \frac{p^2}{q^2}.
\end{align}$$Multiplying both sides of the equation by $q^2$ yields
$$p^2 = 2q^2.$$
From the above lemma we see that $p$ must be even, and so $p=2n$ for some integer $n$. Substituting this, we have that
$$\begin{align}
p^2 &= (2n)^2 \\[1em]
&= 4n^2 \\[1em]
&= 2q^2.
\end{align}$$Canceling a factor of $2$ from the numerator and denominator of that last equality yields
$$q^2 = 2n^2.$$
Again, from the above lemma it follows that $q$ must be even. But then $p$ and $q$ are both even, and so our fraction $\frac{p}{q}$ was not in canonical form — a contradiction.
It follows that there is no rational number $c$ with $c^2=2$.
I now feel justified in calling that length that ought to be $\sqrt{2}$ a gap in the rational number line. It may seem odd that an infinitely dense line would have gaps, but it is irrefutably true. However, we still have yet to fully classify the nature of these gaps, and that is what the remainder of this post will aim to achieve. On top of that, we are no closer to filling them in than we were when we started, and I will attempt to cover that topic in the next two posts. To do all of this, we will need to introduce a few new tools.
Cauchy Sequences
I've talked about sequences and convergence in a topological setting previously (here). Since we are now restricting our attention to the rational numbers, I will rephrase the definition of a convergent sequence slightly.
Definition. A sequence $(x_k)_{k\in\N}$ of rational numbers converges to a point $x\in\Q$ if for every rational number $\epsilon>0$ there is some natural number $N$ for which $\abs{x-x_k}<\epsilon$ whenever $k>N$.
In this case, we say that $x$ is the limit of that sequence and we write $\displaystyle{\lim_{n\to\infty} x_n = x}$.
This would of course be equivalent to the regular topological definition if we were to look at the rational numbers as a subspace of the real numbers. However, we don't have real numbers to work with yet (we are attempting to build them right now) so we have to work with this more specific definition for the time being.
Note that since $\Q$ is a metric space, it is of course Hausdorff and thus if a sequence converges, it does so to a unique limit. That is to say, a sequence of rational numbers either converges to one rational number or it does not converge at all. It cannot converge to multiple limits.
Cauchy sequences are a specific type of sequence which offer an insightful way to understand the gaps in the rational number line. We will explore this idea in the coming paragraphs, but for now let's just have the definition.
Definition. A sequence $(x_k)_{k\in\N}$ of rational numbers is a Cauchy sequence if for every rational number $\epsilon>0$ there is some natural number $N$ for which $\abs{x_n-x_m}<\epsilon$ whenever $n, m>N$.
At first glance, this looks a lot like the definition of convergence. Notice however that the definition of Cauchy sequences makes no reference to a limit. Instead, the requirement is simply that points in the sequence all stay sufficiently close together if we look sufficiently far out.
Is this condition actually any different from the condition of convergence? It might not seem so at first, but it turns out that they are different. As we are about to see, every convergent sequence of rational numbers is a Cauchy sequence, but not every Cauchy sequence of rational numbers converges! I will prove the former first, since it is easier.
Theorem. Every convergent sequence of rational numbers is a Cauchy sequence.
Proof. Suppose $(x_k)_{k\in\N}$ is a sequence of rational numbers which converges to a rational number $x$, and choose any rational number $\epsilon>0$. Then certainly $\frac{\epsilon}{2}$ is also a positive rational number, and so from the definition of convergence it follows that there exists a natural number $N$ for which $\abs{x-x_k}<\frac{\epsilon}{2}$ whenever $k>N$.
Now, choose any two natural numbers $n,m>N$. Then certainly $\abs{x-x_n}<\frac{\epsilon}{2}$ and $\abs{x-x_m}<\frac{\epsilon}{2}$. From the triangle inequality,
$$\begin{align}
\abs{x_n-x_m} &\le \abs{x-x_n} + \abs{x-x_m} \\[1em]
&= \abs{x_n-x} + \abs{x-x_m} \\[1em]
&< \frac{\epsilon}{2} + \frac{\epsilon}{2} \\[1em]
&= \epsilon.
\end{align}$$Thus, $(x_k)_{k\in\N}$ is a Cauchy sequence.
In order to show that not every Cauchy sequence in $\Q$ converges, we just need to exhibit a counterexample. This is easier said than done, however, without appealing to what we already know about real numbers. To elaborate, we could certainly say that the sequence
$$(1,\ 1.4,\ 1.41,\ 1.414,\ 1.4142,\ 1.41421,\ 1.414213,\ \ldots)$$
is a rational sequence, and it is certainly Cauchy since all terms after the $N$th will always be less than $\frac{1}{10^N}$ apart (assuming the indexing starts at zero). Additionally, this sequence does not converge to a rational number, since what it is really converging to is $\sqrt{2}$.
Here's another such example. The sequence
$$\left(\sum_{k=0}^n \frac{1}{k!}\right)_{n=0}^\infty$$
is a rational sequence. It is Cauchy (which I will not prove as it requires some annoying bounding which is outside the scope of this post), but it does not converge to a rational number since it is really converging to Euler's constant, $e$. If you don't believe me, try playing around with this Python code:
(If you must know, this is actually the sequence of partial sums in the Taylor series definition of $e$.)
However, both of the above examples make use of our existing knowledge of the real numbers $\sqrt{2}$ and $e$. We shouldn't really be doing this, since it isn't really fair to use information about real numbers when our goal is to construct them. Unfortunately, this is one place where I am going to have to cheat since a more rigorous treatment of this phenomenon of Cauchy sequences not converging in $\Q$ would require a lot more machinery than I am ready to cover.
What is now apparent, though, is that we have classified the gaps that exist in the rational number line. Any rational Cauchy sequence that does not converge to a rational number indicates the presence of such a gap.
I like to think of it this way: if it is possible for points in a space to get closer and closer together until eventually they poof out of the space entirely, then there's definitely something missing from that space.
The following definition is useful in discussing this phenomenon. I will make it broader than strictly necessary by defining it on arbitrary metric spaces.
Definition. A metric space $X$ is complete if every Cauchy sequence in $X$ converges to a point in $X$.
By this definition and the counterexamples above, we can immediately see that $\Q$ is not a complete metric space. Our aim is to, well, complete it. Doing so will get us the real number system. This procedure is what I will cover in my next post on the subject.
Least Upper Bounds
There is an alternative, but equivalent, method of classifying these pesky gaps in the rational number line. Their equivalence is not too difficult to show, and I may or may not prove it for you at some point depending on how long this series of posts ends up being. We will begin our journey toward this new approach by making a few definitions.
Definition. Let $A$ be any subset of $\Q$. Then a point $x\in\Q$ is an upper bound of $A$ if $x\ge a$ for every $a\in A$.
If $A$ has an upper bound, we say that it is bounded above.
There is a corresponding definition of lower bound that can be obtained by simply reversing the inequality, but for the sake of our construction and intuition it is necessary only to study upper bounds.
Notice that a subset $A\subseteq\Q$ might have many upper bounds. For instance, $A=\{0\}$ is certainly a subset of $\Q$, and any nonnegative rational number is an upper bound of $A$. Of course, this also shows that an upper bound for a set does not need to be contained in that set. Also worth noting is that every rational number is vacuously an upper bound of the empty set.
If a subset of $\Q$ has a bunch of upper bounds but one of those upper bounds happens to be smaller than all the others, there are a few names for it.
Definition. Let $A$ be any subset of $\Q$. Then a point $x\in\Q$ is the supremum (or least upper bound) of $A$ if it is an upper bound of $A$ and $x\le y$ for every upper bound $y$ of $A$.
Again, there is a corresponding definition of infimum (or greatest lower bound) by reversing everything, but we will not need it for our purposes.
It is easy to show that if a subset of $\Q$ has a supremum then it is unique, so I will not do that here. It is also clear that a subset of $\Q$ can only possess a supremum if it is nonempty and bounded above. The question then is whether every such set has a supremum? The answer may surprise you!!! (It won't. The answer is no.)
Let's make one more definition in order to simplify our impending discussion.
Definition. A partially ordered set $X$ has the least upper bound property if every nonempty subset of $X$ which is bounded above has a supremum.
I've defined it more generally than necessary, but $\Q$ certainly possesses such an order and so it makes sense to ask whether or not it has the least upper bound property. As I mentioned before, it does not, and our reasoning here is similar to my above reasoning that $\Q$ is not complete.
Here's our counterexample: $A=\{x\in\Q \mid x^2<2\}$, the set of rational numbers whose square is less than $2$ (or you may think of this intuitively as the set of rational numbers with absolute value less than $\sqrt{2}$). This set is certainly nonempty, since it contains $0$ and $1$ at the very least. It is also bounded above by $2$ and in fact by any rational number whose square is greater than $2$.
I claim that our set $A$ has no supremum in $\Q$. Let's prove this.
Theorem. The set $A=\{x\in\Q \mid x^2<2\}$ has no supremum in $\Q$.
Proof. We proceed by contradiction, supposing that there exists a supremum $x\in\Q$ of $A$. Define
$$\begin{align}
y &= x - \frac{x^2-2}{x+2} \\[.5em]
&= \frac{2(x+1)}{x+2}.
\end{align}$$We do not need to worry about the denominator being $0$ because $-2$ is certainly not a supremum for $A$ (that is, we know $x\ne -2$). For reasons that will become clear shortly, we note that
$$y^2 = \frac{4(x+1)^2}{(x+2)^2},$$
and thus
$$\begin{align}
y^2-2 &= \frac{4(x+1)^2}{(x+2)^2} - \frac{2(x+2)^2}{(x+2)^2} \\[.5em]
&= \frac{4(x^2+2x+1)-2(x^2+4x+4)}{(x+2)^2} \\[.5em]
&= \frac{4x^2 + 8x + 4 - 2x^2 - 8x - 8}{(x+2)^2} \\[.5em]
&= \frac{2x^2-4}{(x+2)^2} \\[.5em]
&= \frac{2(x^2-2)}{(x+2)^2}.
\end{align}$$By the law of trichotomy for partial orders, precisely one of the following three cases is true:
- $x^2 < 2$,
- $x^2 = 2$,
- $x^2 > 2$.
I will show that each of the above cases leads to a contradiction.
We consider case 1 first. If $x^2 < 2$ then certainly $x^2-2 < 0$. It follows then from the definition of $y$ that $y>x$. However, we also see that $y^2-2 <0$ or, equivalently, $y^2<2$ and thus $y\in A$. However, since $y>x$ it cannot be that $x$ is an upper bound for $A$, and thus it is certainly not a supremum of $A$ — a contradiction.
Next, we consider case 2. If $x^2 = 2$ then we have already reached a contradiction, since I showed earlier that there is no such rational number.
Lastly, we consider case 3, which is practically symmetrical to case 1. If $x^2>2$ then certainly $x^2-2>0$. It follows then from the definition of $y$ that $y<x$. However, we also see that $y^2-2>0$ or, equivalently, $y^2>2$ and thus $y$ is an upper bound for $A$. However, $y<x$ and thus $x$ is certainly not a supremum of $A$ (since there exists an upper bound for $A$ that is smaller than $x$). Thus, we have reached a contradiction.
Since all possible cases lead to a contradiction, the result follows.
This counterexample shows us that $\Q$ does not have the least upper bound property! This indicates that it is full of gaps. Namely, any nonempty subset of $\Q$ that is bounded above but does not possess a supremum indicates the presence of a gap. Filling in these gaps to construct a number system ($\R$) that does have the least upper bound property will be the focus of my third post in this series.
Until next time!