21. The Real Numbers¶
21.1. The Number Systems¶
We have already come across some of the fundamental number systems: the natural numbers, \(\mathbb{N}\), the integers, \(\mathbb{Z}\), and the rationals, \(\mathbb{Q}\). In a sense, each subsequent element of the list was designed to remedy defects in the previous system. We can subtract any integer from any other integer and end up with another integer, and we can divide any rational number by a nonzero rational number and end up with a rational number.
The integers satisfy all of the following properties:
Addition is associative and commutative.
There is an additive identity, \(0\), and every element \(x\) has an additive inverse, \(-x\).
Multiplication is associative and commutative.
There is a multiplicative identity, \(1\).
Multiplication distributes over addition: for every \(x\), \(y\), and \(z\), we have \(x (y + z) = x y + x z\).
The ordering \(\leq\) is a total order.
For any elements \(x\), \(y\), and \(z\), if \(x \leq y\) then \(x + z \leq y + z\).
For any elements \(x\) and \(y\), if \(0 \leq x\) and \(0 \leq y\) then \(0 \leq x y\).
The first five clauses say that with \(\times\), \(+\), \(0\), and \(1\), the integers form a commutative ring, and the last three say that together with \(\leq\), the structure is an ordered ring. The natural numbers lack additive inverses, so they satisfy a slightly weaker set of axioms that make them an ordered semiring. On the other hand, the rational numbers also form an ordered ring, satisfying the following additional property:
Every nonzero element has a multiplicative inverse, \(x^{-1}\).
This makes them an instance of an ordered field.
It is worth knowing that once we have the natural numbers, it is possible to construct the integers and rational numbers, using set-theoretic constructions you have already seen. For example, we can take an integer to be a pair \((i, n)\) of natural numbers where \(i\) is either 0 or 1, with the intention that \((0, n)\) represents the positive integer \(n\), and \((1, n)\) represents the negative integer \(-(n+1)\). (We use \(-(n+1)\) instead of \(-n\) to avoid having two representations of \(0\).) With this definition, the integers are simply \(\{0, 1\} \times \mathbb{N}\). We can then go on to define the operations of addition and multiplication, the additive inverse, and the order relation, and prove they have the desired properties.
This construction has the side effect that the natural numbers themselves are not integers; for example, we have to distinguish between the natural number \(2\) and the integer \(2\). This is the case in Lean. In ordinary mathematics, it is common to think of the natural numbers as a subset of the integers. Once we construct the integers, however, we can throw away the old version of the natural numbers, and afterwards identify the natural numbers as nonnegative integers.
We can do the same for the rationals, defining them to be the set of pairs \((a, b)\) in \(\mathbb{Z} \times \mathbb{N}\), where either \(a = 0\) and \(b = 1\), or \(b > 0\) and \(a\) and \(b\) have no common divisor (other than \(1\) and \(-1\)). The idea is that \((a, b)\) represents \(a / b\). With this definition, the rationals are really a subset of \(\mathbb{Z} \times \mathbb{N}\), and we can then define all the operations accordingly.
In the next section, we will define a more sophisticated approach, one which will scale to a definition of the real numbers. And in a later chapter, we will show how to construct the natural numbers from the axioms of set theory. This shows that we can construct all the number systems from the bottom up.
But first, let us pause for a moment to consider why the real numbers are needed. We have seen that \(2\) has no rational square root. This means, in a sense, that there is a “gap” in the rationals: there are rationals whose squares are arbitrarily close to 2, but there is no rational \(x\) with the property that \(x^2 = 2\). But it seems intuitively clear that there should be some number with that property: \(\sqrt{2}\) is the length of the diagonal of a square with side length \(1\). Similarly, \(\pi\), the area of a circle with radius 1, is missing from the rationals. These are the kinds of defects that the real numbers are designed to repair.
You may be used to thinking of real numbers as (potentially) infinite decimals: for example, \(\sqrt{2} = 1.41421356\ldots\) and \(\pi = 3.14159265\ldots\). A central goal of this chapter is to make the “…” precise. The idea is that we can take an infinite decimal to represent a sequence of rational approximations. For example, we can approximate the square root of 2 with the sequence \(1, 1.4, 1.41, 1.414, \ldots\). We would like to define \(\sqrt{2}\) to be the “limit” of that sequence, but we have seen that the sequence does not have a limit in the rationals. So we have to construct new objects, the real numbers, to serve that purpose.
In fact, we will define the real numbers, more or less, to be such sequences of rational approximations. But we will have to deal with the fact that, for example, there are lots of ways of approximating the square root of two. For example, we can just as well approach it from above, \(2, 1.5, 1.42, \ldots\), or by oscillating above and below. The next section will show us how to “glue” all these sequences together and treat them as a single object.
21.2. Quotient Constructions¶
Let \(A\) be any set, and let \(\equiv\) be any equivalence relation on \(A\). Recall from Section 13.3 that we can assign to every element \(a\) of \(A\) the equivalence class \([a]\), where \(b \in [a]\) means \(b \equiv a\). This assignment has the property that for every \(a\) and \(b\), \(a \equiv b\) if and only if \([a] = [b]\).
Given any set \(A\) and equivalence relation \(\equiv\), define \(A / \mathord{\equiv}\) to be the set \(\{ [ a ] \mid a \in A \}\) of equivalence classes of \(A\) modulo \(\equiv\). This set is called “\(A\) modulo \(\mathord{\equiv}\),” or the quotient of \(A\) by \(\equiv\). You can think of this as the set \(A\) where equivalent elements are “glued together” to make a coarser set.
For example, if we consider the integers \(\mathbb{Z}\) with \(\equiv\) denoting equivalence modulo 5 (as in Section 19.4), then \(\mathbb{Z} / \mathord{\equiv}\) is just \(\{ [0], [1], [2], [3], [4] \}\). We can define addition on \(\mathbb{Z} / \mathord{\equiv}\) by \([a] + [b] = [a + b]\). For this definition to make sense, it is important to know that the right-hand side does not depend on which representatives of \([a]\) and \([b]\) we choose. In other words, we need to know that whenever \([a] = [a']\) and \([b] = [b']\), then \([a + b] = [a' + b']\). This, in turn, is equivalent to saying that if \(a \equiv a'\) and \(b \equiv b'\), then \(a + b \equiv a' + b'\). In other words, we require that the operation of addition respects the equivalence relation, and we saw in Section 19.4 that this is in fact the case.
This general strategy for transferring a function defined on a set to a function defined on a quotient of that set is given by the following theorem.
Theorem. Let \(A\) and \(B\) be any sets, let \(\equiv\) be any equivalence relation defined on \(A\), and let \(f : A \to B\). Suppose \(f\) respects the equivalence relation, which is to say, for every \(a\) and \(a'\) in \(A\), if \(a \equiv a'\), then \(f(a) = f(a')\). Then there is a unique function \(\bar f : A / \mathord{\equiv} \to B\), defined by \(\bar f ([a]) = f(a)\) for every \(a\) in \(A\).
Proof. We have defined the value of \(\bar f\) on an equivalence class \(x\) by writing \(x = [a]\), and setting \(\bar f(x) = f(a)\). In other words, we say that \(\bar f(x) = y\) if and only if there is an \(a\) such that \(x = [a]\), and \(f(a) = y\). What is dubious about the definition is that, a priori, it might depend on how we express \(x\) in that form; in other words, we need to show that there is a unique \(y\) meeting this description. Specifically, we need to know that if \(x = [a] = [a']\), then \(f(a) = f(a')\). But since \([a] = [a']\) is equivalent to \(a \equiv a'\), this amounts to saying that \(f\) respects the equivalence relation, which is exactly what we have assumed.
Mathematicians often “define” \(\bar f\) by the equation \(\bar f ([a])= f(a)\), and then express the proof above as a proof that “\(\bar f\) is well defined.” This is confusing. What they really mean is what the theorem says, namely, that there is a unique function meeting that description.
To construct the integers, start with \(\mathbb{N} \times \mathbb{N}\). Think of the pair of natural numbers \((m, n)\) as representing \(m - n\), where the subtraction takes place in the integers (which we haven’t constructed yet!). For example, both \((2, 5)\) and \((6, 9)\) represent the integer \(-3\). Intuitively, the pairs \((m, n)\) and \((m', n')\) will represent the same integer when \(m - n = m' - n'\), but we cannot say this yet, because we have not yet defined the appropriate notion of subtraction. But the equation is equivalent to \(m + n' = m' + n\), and this makes sense with addition on the natural numbers.
Definition. Define the relation \(\equiv\) on \(\mathbb{N} \times \mathbb{N}\) by \((m, n) \equiv (m', n')\) if and only if \(m + n' = m' + n\).
Proposition. \(\equiv\) is an equivalence relation.
Proof. For reflexivity, it is clear that \((m, n) \equiv (m, n)\), since \(m + n = m + n\).
For symmetry, suppose \((m, n) \equiv (m', n')\). This means \(m + n' = m' + n\). But the symmetry of equality implies \((m', n') \equiv (m, n)\), as required.
For transitivity, suppose \((m, n) \equiv (m', n')\), and \((m', n') = (m'', n'')\). Then we have \(m + n' = m' + n\) and \(m' + n'' = n' + m''\). Adding these equations, we get
Subtracting \(m' + n'\) from both sides, we get \(m + n'' = n + m''\), which is equivalent to \((m, n) = (m'', n'')\), as required.
We can now define the integers to be \(\mathbb{N} \times \mathbb{N} / \mathord{\equiv}\). How should we define addition? If \([(m, n)]\) represents \(m - n\), and \([(u, v)]\) represents \(u - v\), then \([(m, n)] + [(u, v)]\) should represent \((m + u) - (n + v)\). Thus, it makes sense to define \([(m, n)] + [(u, v)]\) to be \([(m + u), (n + v)]\). For this to work, we need to know that the operation which sends \((m, n)\) and \((u, v)\) to \((m + u, n + v)\) respects the equivalence relation.
Proposition. If \((m, n) \equiv (m', n')\) and \((u, v) \equiv (u', v')\), then \((m + u, n + v) \equiv (m' + u', n' + v')\).
Proof. The first equivalence means \(m + n' = m' + n\), and the second means \(u + v' = u' + v\). Adding the two equations, we get \((m + u) + (n' + v') \equiv (m' + u') + (n + v)\), which is exactly the same as saying \((m + u, n + v) \equiv (m' + u', n' + v')\).
Every natural number \(n\) can be represented by the integer \([(n, 0)]\), and, in particular, \(0\) is represented by \([(0, 0)]\). Moreover, if \([(m, n)]\) is any integer, we can define its negation to be \([(n, m)]\), since \([(m, n)] + [(n, m)] = [(m + n, n + m)] = [(0, 0)]\), since \((m + n, n + m) \equiv (0, 0)\). In short, we have “invented” the negative numbers!
We could go on this way to define multiplication and the ordering on the integers, and prove that they have the desired properties. We could also carry out a similar construction for the rational numbers. Here, we would start with the set \(\mathbb{Z} \times \mathbb{Z}^{>0}\), where \(\mathbb{Z}^{>0}\) denotes the strictly positive integers. The idea, of course, is that \((a, b)\) represents \((a / b)\). With that in mind, it makes sense to define \((a, b) \equiv (c, d)\) if \(a d = b c\). We could go on to define addition, multiplication, and the ordering there, too. The details are tedious, however, and not very illuminating. So we turn, instead, to a construction of the real numbers.
21.3. Constructing the Real Numbers¶
The problem we face is that the sequence \(1, 1.4, 1.41, 1.414, 1.4142, \ldots\) of rational numbers seems to approach a value that would be the square root of 2, but there is no rational number that can play that role. The next definition captures the notion that this sequence of numbers “seems to approach a value,” without referring to a value that it is approaching.
Definition. A sequence of rational numbers \((q_i)_{i \in \mathbb{N}}\) is Cauchy if for every rational number \(\varepsilon > 0\), there is some natural number \(N \in \mathbb{N}\) such that for all \(i, j \geq N\), we have that \(|q_i - q_j| < \varepsilon\).
Roughly speaking, a Cauchy sequence is one where the elements become arbitrarily close, not just to their successors, but to all following elements. It is common in mathematics to use \(\varepsilon\) to represent a quantity that is intended to denote something small; you should read the phrase “for every \(\varepsilon > 0\)” as saying “no matter how small \(\varepsilon\) is.” So a sequence is Cauchy if, for any \(\varepsilon > 0\), no matter how small, there is some point \(N\), beyond which the elements stay within a distance of \(\varepsilon\) of one another.
Cauchy sequences can be used to describe these gaps in the rationals, but, as noted above, many Cauchy sequences can be used to describe the same gap. At this stage, it is slightly misleading to say that they “approach the same point,” since there is no rational point that they approach; a more precise statement is that the sequences eventually become arbitrarily close.
Definition. Two Cauchy sequences \(p = (p_i)_{i \in \mathbb{N}}\) and \(q = (q_i)_{i \in \mathbb{N}}\) are equivalent if for every rational number \(\varepsilon > 0\), there is some natural number \(N \in \mathbb{N}\) such that for all \(i \geq N\), we have that \(|p_i - q_i| < \varepsilon\). We will write \(p \equiv q\) to express that \(p\) is equivalent to \(q\).
Proposition. \(\equiv\) is an equivalence relation on Cauchy sequences.
Proof. Reflexivity and symmetry are easy, so let us prove transitivity. Suppose \((p_i) \equiv (q_i)\) and \((q_i) \equiv (r_i)\). We want to show that the sequence \((p_i)\) is equivalent to \((r_i)\). So, given any \(\varepsilon > 0\), choose \(N_0\) large enough such that for every \(i \ge N_0\), \(|p_i - q_i| < \varepsilon / 2\). Choose another number, \(N_1\), so that for every \(i \geq N_1\), \(|q_i - r_i| < \varepsilon / 2\). Let \(N = \max(N_0, N_1)\). Then for every \(i \geq N\), we have
as required.
Notice that the proof uses the triangle inequality, which states for any rational numbers \(a\) and \(b\), \(|a + b| \leq |a| + |b|\). If we define \(|a|\) to be the maximum of \(a\) and \(-a\), the triangle inequality in fact holds for any ordered ring:
Theorem. Let \(a\) and \(b\) be elements of any ordered ring. Then \(|a + b| \leq |a| + |b|\).
Proof. By the definition of absolute value, it suffices to show that \(a + b \leq |a| + |b|\) and \(-(a + b) \leq |a| + |b|\). The first claim follows from the fact that \(a \leq |a|\) and \(b \leq |b|\). For the second claim, we similarly have \(-a \leq |a|\) and \(-b \leq |b|\), so \(-(a + b) = -a + - b \leq |a| + |b|\).
In the theorem above, if we let \(a = x - y\) and \(b = y - z\), we get \(|x - z| \leq |x - y| + |y - z|\). The fact that \(|x - y|\) represents the distance between \(x\) and \(y\) on the number line explains the name: for any three “points” \(x\), \(y\), and \(z\), the distance from \(x\) to \(z\) can’t be any greater than the distance from \(x\) to \(y\) plus the distance from \(y\) to \(z\).
We now let \(A\) be the set of Cauchy sequences of rationals, and define the real numbers, \(\mathbb{R}\), to be \(A / \mathord{\equiv}\). In other words, the real numbers are the set of Cauchy sequence of rationals, modulo the equivalence relation we just defined.
Having the set \(\mathbb{R}\) by itself is not enough: we also would like to know how to add, subtract, multiply, and divide real numbers. As with the integers, we need to define operations on the underlying set, and then show that they respect the equivalence relation. For example, we will say how to add Cauchy sequences of rationals, and then show that if \(p_1 \equiv p_2\) and \(q_1 \equiv q_2\), then \(p_1 + q_1 \equiv p_2 + q_2\). We can then lift this definition to \(\mathbb{R}\) by defining \([p] + [q]\) to be \([p + q]\).
Luckily, it is easy to define addition, subtraction, and multiplication on Cauchy sequences. If \(p = (p_i)_{i \in \mathbb{N}}\) and \(q = (q_i)_{i \in \mathbb{N}}\) are Cauchy sequences, let \(p + q = (p_i + q_i)_{i \in \mathbb{N}}\), and similarly for subtraction and multiplication. It is trickier to show that these sequences are Cauchy themselves, and to show that the operations have the appropriate algebraic properties. We ask you to prove some of these properties in the exercises.
We can identify each rational number \(q\) with the constant Cauchy sequence \(q, q, q, \ldots\), so the real numbers include all the rationals. The next step is to abstract away the details of the particular construction we have chosen, so that henceforth we can work with the real numbers abstractly, and no longer think of them as given by equivalence classes of Cauchy sequences of rationals.
21.4. The Completeness of the Real Numbers¶
We constructed the real numbers to fill in the gaps in the rationals. How do we know that we have got them all? Perhaps we need to construct even more numbers, using Cauchy sequences of reals? The next theorem tells us that, on the contrary, there is no need to extend the reals any further in this way.
Definition. Let \(r\) be a real number. A sequence \((r_i)_{i \in \mathbb{N}}\) of real numbers converges to \(r\) if, for every \(\varepsilon > 0\), there is an \(N\) such that for every \(i \geq N\), \(|r_i - r| < \varepsilon\).
Definition. A sequence \((r_i)_{i \in \mathbb{N}}\) converges if it converges to some \(r\).
Theorem. Every Cauchy sequence of real numbers converges.
The statement of the theorem is often expressed by saying that the real numbers are complete. Roughly, it says that everywhere you look for a real number, you are bound to find one. Here is a similar principle.
Definition. An element \(u \in \mathbb{R}\) is said to be an upper bound to a subset \(S \subseteq \mathbb{R}\) if everything in \(S\) is less than or equal to \(u\). \(S\) is said to be bounded if there is an upper bound to \(S\). An element \(u\) is said to be a least upper bound to \(S\) if it is an upper bound to \(S\), and nothing smaller than \(u\) is an upper bound to \(S\).
Theorem. Let \(S\) be a bounded, nonempty subset of \(\mathbb{R}\). Then \(S\) has a least upper bound.
The rational numbers do not have this property: if we set \(S = \{x \in \mathbb{Q} \mid x^2 < 2\}\), then the rational number 2 is an upper bound for \(S\), but \(S\) has no least upper bound in \(\mathbb{Q}\).
It is a fundamental theorem that the real numbers are characterized exactly by the property that they are a complete ordered field, such that every real number \(r\) is less than or equal to some natural number \(N\). Any two models that meet these requirements must behave in exactly the same way, at least insofar as the constants \(0\) and \(1\), the operations \(+\) and \(*\), and the relation \(\leq\) are concerned. This fact is extremely powerful because it allows us to avoid thinking about the Cauchy sequence construction in normal mathematics. Once we have shown that our construction meets these requirements, we can take \(\mathbb{R}\) to be “the” unique complete totally ordered field and ignore any implementation details. We are also free to implement \(\mathbb{R}\) in any way we choose, and as long as it meets this interface, and as long as they do not refer to the underlying representations, any theorems we prove about the reals will hold equally well for all constructions.
21.5. An Alternative Construction¶
Many sources use an alternative construction of the reals, taking them instead to be Dedekind cuts. A Dedekind cut is an ordered pair \((A, B)\) of sets of rational numbers with the following properties:
Every rational number \(q\) is in either \(A\) or \(B\).
Each \(a \in A\) is less than every \(b \in B\).
There is no greatest element of \(A\).
\(A\) and \(B\) are both nonempty.
The first two properties show why we call this pair a “cut.” The set \(A\) contains all of the rational numbers to the left of some mark on the number line, and \(B\) all of the points to the right. The third property tells us something about what happens exactly at that mark. But there are two possibilities: either \(B\) has a least element, or it doesn’t. Picturing the situation where \(A\) has no greatest element and \(B\) has no least element may be tricky, but consider the example \(A = \{x \in \mathbb{Q} \mid x^2 < 2\}\) and \(B = \{x \in \mathbb{Q} \mid x^2 > 2\}\). There is no rational number \(q\) such that \(q^2 = 2\), but there are rational numbers on either side that are arbitrarily close; thus neither \(A\) nor \(B\) contains an endpoint.
We can define \(\mathbb{R}\) to be the set of Dedekind cuts. A Dedekind cut \((A, B)\) corresponds to a rational number \(q\) if \(q\) is the least element of \(B\), and to an irrational number if \(B\) has no least element. It is straightforward to define addition on \(\mathbb{R}\):
Some authors prefer this construction to the Cauchy sequence construction because it avoids taking the quotient of a set, and thus removes the complication of showing that arithmetic operations respect equivalence. Others prefer Cauchy sequences since they provide a clearer notion of approximation: if a real number \(r\) is given by a Cauchy sequence \((q_i)_{i \in \mathbb{N}}\), then an arbitrarily close rational approximation of \(r\) is given by \(q_N\) for a sufficiently large \(N\).
For most mathematicians most of the time, though, the difference is immaterial. Both constructions create complete linear ordered fields, and in a certain sense, they create the same complete linear ordered field. Strictly speaking, the set of Cauchy reals is not equal to the set of Dedekind reals, since one consists of equivalence classes of rational Cauchy sequences and one consists of pairs of sets of rationals. But there is a bijection between the two sets that preserves the field properties. That is, there is a bijection \(f\) from the Cauchy reals to the Dedekind reals such that
\(f(0)=0\)
\(f(1)=1\)
\(f(x+y)=f(x)+f(y)\)
\(f(x \cdot y)=f(x) \cdot f(y)\)
\(f(-x)=-f(x)\)
\(f(x^{-1})=f(x)^{-1}\)
\(f(x) \leq f(y) \iff x \leq y\)
We say that the two constructions are isomorphic, and that the function \(f\) is an isomorphism. Since we often only care about the real numbers in regard to their status as a complete ordered field, and the two constructions are indistinguishable as ordered fields, it makes no difference which construction is used.
21.6. Exercises¶
Show that addition for the integers, as defined in Section 21.2, is commutative and associative.
Show from the construction of the integers in Section 21.2 that \(a + 0 = a\) for every integer \(a\).
Define subtraction for the integers by \(a - b = a + (-b)\), and show that \(a - b + b = a\) for every pair of integers \(a\) and \(b\).
Define multiplication for the integers, by first defining it on the underlying representation and then showing that the operation respects the equivalence relation.
Show that every Cauchy sequence is bounded: that is, if \((q_i)_{i \in \mathbb{N}}\) is Cauchy, there is some rational \(M\) such that \(|q_i| \leq M\) for all \(i\). Hint: try letting \(\varepsilon = 1\).
Let \(p = (p_i)_{i \in \mathbb{N}}\) and \(q = (q_i)_{i \in \mathbb{N}}\) be Cauchy sequences. Define \(p + q = (p_i + q_i)_{i \in \mathbb{N}}\) and \(p q = (p_i q_i)_{i \in \mathbb{N}}\).
Show that \(p + q\) is Cauchy. That is, for arbitrary \(\varepsilon > 0\), show that there exists an \(N\) such that for all \(i, j \geq N\), \(|(p_i + q_i) - (p_j + q_j)| < \varepsilon\).
Show that \(p q\) is Cauchy. In addition to the triangle inequality, you will find the previous exercise useful.
These two parts show that addition of Cauchy sequences respects equivalence.
Show that if \(p, p', q\) are Cauchy sequences and \(p \equiv p'\), then \(p + q \equiv p' + q\).
Using the first part of this problem, show that if \(p, p', q, q'\) are Cauchy sequences, \(p \equiv p'\), and \(q \equiv q'\), then \(p + q \equiv p' + q'\). You can use the fact that addition on the real numbers is commutative.
Show that if \((A_1, B_1)\) and \((A_2, B_2)\) are Dedekind cuts, then \((A_1, B_1) + (A_2, B_2)\) is also a Dedekind cut.