5 Completeness
Highlights of this Chapter: We look to formalize the notion of limit used by the babylonians and archimedes, and come to the Nested Interval Property. We see that this property does not hold in \(\QQ\), so we must seek another axiom which implies us. This leads us to bounds, infima, and suprema. We study the properties of this new definition, use it to define completeness, and show completeness does indeed imply the nested interval property, as we wished.
Now that we have axiomatized the notion of a ‘number line’ as an ordered field, it’s time to try and figure out how to describe “completed” infinite processes in a formal way. This is an inherently slippery notion, as it runs into the difficulty of “talking about infinity, without saying infinity” that lies at the heart of analysis.
So, before introducing the abstract tools that end up best suited for this task (the infimum and supremum), we’ll begin with some motivational exploration, and think about what sort of theorems we would want to be true in a number system that allows one to do infinite constructions.
5.1 Dreaming of Infinity
Archimedes idea for calculating \(\pi\) was to give an upper bound and a lower bound for the area of a circle, in terms of the area \(a_n\) of an inscribed polygon and a circumscribed polygon \(A_n\). This provided an interval that archimedes hoped to trap \(\pi\) inside of, each time \(n\) grows, \(a_n\) grows and \(A_n\) shrinks - so the confidence interval of Archimedes shrinks!
\[\cdots [a_6,A_6]\supset [a_{12},A_{12}]\supset [a_{24},A_{24}]\supset \cdots\]
A collection of intervals like this is called nested:
Definition 5.1 (Nested Intervals) A sequence of intervals \(I_1, I_2,I_3,\ldots\) in an ordered field is called nested if for all \(n\), \(I_{n+1}\subseteq I_n\).
As these nested intervals shrink in size, the hope is that they zero in on \(\pi\) exactly: mathematically we might express this with an intersection over all intervals (where the question mark over the equals means we have not proven this, but hope its true)
\[\bigcap_{n}[a_n,A_n]\stackrel{?}{=}\{\pi\}\]
The babylonian process approximating \(\sqrt{2}\) can also be recast in terms of a sequence of nested intervals: where we take the two sides \(w_n,h_n\) (width and height) of each approximating rectangle as a confidence interval around \(\sqrt{2}\). We of course want, that in the limit this zeroes in directly on the square root,
\[\bigcap_{n}[w_n,h_n]\stackrel{?}{=}\{\sqrt{2}\}\]
In formulating any of these processes (pre-rigorously, say, in antiquity) mathematicians always assumed without proof that if you had a collection of shrinking intervals, they were shrinking around some real number that could be captured after infinitely many steps. One way to formalize this hope would be the following ‘dream theorem’.
Dream Theorem: In a complete number system, every sequence of nested intervals has a nonempty intersection.
This sort ‘dream result’ has a strange but important status in mathematics: its not a theorem we can prove right now, but rather a guiding light as we march forward. We should investigate our current axioms and ask if they can prove this - and, if not, we should look for additional axioms to improve our notion of number line until we can!
How do we tell if our current axioms imply this dream theorem? In a situation like this, mathematicians may try to ask what sort of things satisfy the current axioms and look at these for inspiration. Here - the rational numbers satisfy the axioms of an ordered field, and this provides a big hint: Pythagoras proved that there is no rational square root of 2, which implies the Babylonian process does not zero in on any number at all, but rather at infinity reaches nothing!
\[\bigcap_{n}[w_n,h_n]=\varnothing\]
Because there is at least one ordered field (the rationals) that does not satisfy the dream theorem, we know that these axioms are not enough.
The axioms of an ordered field are not enough to deal with completed infinity: there are ordered fields in which the dream theorem is false.
This tells us we must look to extend our axiom system and search out a new axiom that will help our number system capture the slippery notion of infinite processes. Happily, it turns out a productive approach to this grows naturally out of our discussion of nested intervals. But, to decrease the complexity instead of focusing on the entire interval \([\ell_n, u_n]\), we will look separately at the sequence of lower bounds \(\ell_n\) and upper bounds \(u_n\). Understanding the behavior of either of these will turn out to be enough to extend our axiom system appropriately.
5.2 Suprema and Infima
A confidence interval like \([\textrm{width}_n,\textrm{height}_n]\) or \([\textrm{inscribed}_n,\textrm{circumscribed}_n]\) gives us for each \(n\) both an upper bound for the number we are after, and a lower bound.
It will be useful to describe these concepts more precisely.
Definition 5.2 (Bounds) Let \(S\) be a nonempty subset of an ordered field. An upper bound for \(S\) is an element \(u\in\FF\) greater than or equal to all the elements of \(S\): \[\forall s\in S\, s\leq u\] A lower bound for \(S\) is an element \(\ell\in \FF\) which is less than or equal to all the elements of \(S\): \[\forall s\in S\, \ell \leq u\]
\(S\) is said to be bounded above if there exists an upper bound, and to be bounded below if there exists a lower bound. If \(S\) is both bounded above and below, then \(S\) is said to be bounded.
Definition 5.3 (Maximum & Minimum) Let \(S\) be a nonempty subset of an ordered field. Then \(S\) has a $maximum* if there is an element of \(M\in S\) that is also an upper bound for \(S\), and a minimum if some element \(m\) is also a lower bound for \(S\).
The maximum and minimum elements of a set are the best possible upper and lower bounds when they exist: after all, you couldn’t hope to find a smaller lower bound than the maximum, as the maximum would be greater than it, so it couldn’t be an upper bound! While maxima and minima always exist for finite sets things get trickier with infinity. For example, the open interval \((0,1)\) of rational numbers does not have any maximum element.
The correct generalization of maximum to cases like this is called the supremum: the best possible upper bound.
Definition 5.4 (Supremum) Let \(S\) be a set which is bounded above. The least upper bound for \(S\) is a number \(\sigma\) such that
- \(\sigma\) is an upper bound for \(S\)
- If \(u\) is any upper bound, then \(\sigma \leq u\).
When such a least upper bound exists, we call it the supremum of \(S\) and denote it \(\sigma = \sup S\).
This notion of best possible upper bound allows us to rigorously capture the notion of endpoint even for infinite sets that do not have a maximum.
Example 5.1 (A set with no maximum) The set \((0,1)=\{x\in\QQ \mid 0< x<1\}\) has no maximal element, but it does have a supremum in \(\QQ\), namely \(1=\sup S\).
Definition 5.5 (Infimum) The infimum of a set \(S\) is the least upper bound: that is, an element \(\lambda\) where
- \(\lambda\) is a lower bound for \(S\).
- If \(\ell\) is any other lower bound for \(S\), then \(\ell\leq \lambda\).
If such an element exists it is denoted \(\lambda = \inf S\).
Example 5.2
The set \(\NN\) has no upper bounds at all, so \(\sup \NN\) does not exist. It has many lower bounds (like 0, and -14), and its infimum is \(\inf \NN= 1\).
The rational numbers themselves have no upper nor lower bound, so \(\sup\QQ\) and \(\inf\QQ\) do not exist.
Exercise 5.1 Consider the following subsets of the rational numbers. State whether or not they have infima or suprema; when they do, give the inf and sup.
- \([1,3]\)
- \([1,3)\)
- \(\{x\mid x^2<1\}\)
- \(\{x\mid x^3<1\}\)
- \(\{x \mid 1+\frac{1}{n}, n\in\NN \}\)
- \(\{x \mid 1+\frac{(-1)^n}{n},\, n\in\NN\}\)
5.2.1 Infinite Processes
By focusing on one bound at at time, this new terminology lets us rigorously capture the ideas of the babylonians and archimedes, by giving a name to the idealized endpoint of their infinite processes.
Example 5.3 (The Babylonian \(\sqrt{2}\)) Define the set of numbers \(S\) by \(s_0=1\) and \(s_n=\frac{s_n+2/s_n}{2}\), so \[S = \left\{1,\frac{3}{2},\frac{577}{408},\frac{665857}{470832}\ldots\right\}\]
These are all lower bounds for \(\sqrt{2}\) coming from the widths of a rectangle approximating a square that started with side length \(1\). With each increasing \(n\), this approximation gets larger (and better), which gives a hint on how to formalize this in our new vocabulary.
Consider this entire collection as a set \(\{s_0,s_1,s_2,s_3,\ldots, s_n,\ldots\}\) with each \(n\) this set. As the larger elements of this set are better approximations of \(\sqrt{2}\), we can define the result of this infinite process with the least upper bound or supremum \(\sup S\).
Example 5.4 (Inscribed Perimeters of Archimedes) Archimedes’ study of inscribed \(n\)-gons give an ever increasing sequence of areas and perimeters, approaching (but never reaching at any finite stage) the area and perimeter of the unit circle. We review these below:
Let \(p_6 = 6\), and define \(p_{2n}\) recursively as in Example 1.2: \(p_{2n} = 2n\sqrt{2-\sqrt{4-\left(\frac{p_n}{n}\right)^2}}\). Defining \(P\) as the set of numbers produced by this recurrence, \[P=\{p_6,p_{12},p_{24},p_{48},p_{96},\ldots,p_{24576},\ldots\}\]
Each individual number here gives us a lower bound for the circles circumference, as it is computed from a polygon inside the circle. Because this sequence is increasing, larger elements of \(P\) represent better approximations, so we can rigorously define the result after infinitely many doublings as the least upper bound to \(P\), or \(\sup P\).
Example 5.5 (Circumscribed Perimeters of Archimedes) The other side of archimedes’ confidence intervals were computed using circumscribed polygons. Following Exercise 1.10, we precisely define the circumscribed perimeters by setting \(P_4=8\) and using the recurrence \(t_{2n}=\sqrt{1+\frac{1}{t_n^2}}-\frac{1}{t_n}\) for the tangent, to get a recurrence for \(P_{2n}\) in terms of \(P_n\).
This sequence is decreasing as \(n\) grows, so the better estimates for circumference come from the smaller numbers. We formalize this by creating the set \(P\) of all approximate perimeters \[P=\{P_4,P_8,P_{16},P_{32},P_{64},\cdots\}\] and speaking of the final result of the infinite process as the infimum or \(\inf P\)
One reason that suprema and infima are a useful technology to develop is that they are more general than nested intervals: we can make sense of them to talk about any infinite processes, even ones that we naturally have only a lower, or upper estimate for.
Exercise 5.2 Give a formal statement of the Basel problem solved by Euler in terms of infima or suprema.
Exercise 5.3 Give a formal statement of the result of the infinite product of Viete in terms of infima or suprema. Hint: first figure out, as you add new terms to this approximation, is it increasing or decreasing in value?
5.3 Completeness
Because infima and suprema are such a useful tool to precisely describe the final state of certain infinite processes, they are a natural choice of object to concentrate on when looking for an additional axiom for our number system. Indeed - after some thought you can convince yourself that the statement every infinite process that should end in some number, does end in some number is equivalent to the following definition of completeness.
Definition 5.6 (Completeness) An ordered set is complete if every nonempty subset \(S\) that is bounded above has a supremum.
Remark 5.1. One question you might ask yourself is why we chose supremum here, and not infimum - or better, why not both?! It turns out that all of these options are logically equivalent, as you can prove in some exercises below. So, any one of them suffices
We can formalize Pythagoras’ observation about the irrationality of \(\sqrt{2}\) in this language
Theorem 5.1 (\(\QQ\) is not complete) The set \(S=\{s \in\QQ\mid s^2<2\}\) does not have a supremum in \(\QQ\).
Proof (Sketch). A rigorous proof can be given by contradiction: assume that a supremum \(\sigma =\sup S\) exists, and then show that we must have \(\sigma^2=2\) by ruling out the possibilities \(\sigma^2<2\) and \(\sigma^2>2\). The calculations required for these steps are more relevant to the next chapter, so we postpone until then (specifically, Example 6.1 and Exercise 6.4).
Once its known that the supremum must satisfy \(\sigma^2=2\), we apply Pythagoras’ observation (Theorem 1.1) that there are no rational solutions to this equation, to reach a contradiction.
Thus, asking a field to be complete is a constraint above and beyond being an ordered field. So, this is a good candidate for an additional axiom! But before we too hastily accept it, we should check that it actually solves our problem:
Theorem 5.2 (Nested Interval Property) Let \(\FF\) be an ordered field which is also complete, and \(I_0,I_1,I_2,\ldots,I_n,\ldots\) be a collection of nested closed intervals. Then their intersection is nonempty: \[\bigcap_{n\geq 0} I_n \neq \varnothing\]
Proof. Let \(I_n=[a_n,b_n]\). We need to use the fact that \(\FF\) is complete to help us find a number which lies in \(I_n\) for every \(n\). One idea - consider the set of lower endpoints \[A=\{a_1,a_2,a_3,\ldots, a_n,\ldots\}\] This set is nonempty, and because the intervals are nested any one of the \(b_n\)’s serves as an upper bound for \(A\).
By completeness the supremum must exist: lets call this \(\alpha = \sup A\). Now we just need to see that \(\alpha\in I_n=[a_n,b_n]\) for all \(n\). Fix some \(n\): then as \(a_n\in A\) and \(\alpha\) is an upper bound, we know that \(a_n\leq \alpha\). But \(b_n\) is an upper bound for \(A\) so the least upper bound must satisfy \(\alpha\leq b_n\). Putting these together \[a_n\leq \alpha\leq b_n\,\implies\, \alpha\in I_n\] And, since this holds for all natural numbers \(n\), we actually have \(\alpha\in \bigcap_n I_n\), so the intersection is nonempty.
We can even take these tools farther, and see that infima and suprema can tell us exactly to a process that produces confidence intervals \([a_n,b_n]\) after infinitely many steps: if \(A\) is the set of lower endpoints and \(B\) is the set of upper endpoints, we can prove (1) \(\sup A\) and \(\inf B\) both exist, and (2) if the lengths of the intervals \(I_n\) tend to zero, then the nested intersection actually contains just a single point: the number we are after!
This is exactly the validation we needed: while ordered fields do not have enough structure to formalize the infinite processes undertaken in mathematics, complete ordered fields do satisfy the dream theorem! We will study their properties intensively in the next chapter. But for now, we turn to the concept of supremum and infimum themselves, as these seemingly simple ideas will underlie our entire theory of the real numbers.
Exercise 5.4 The proof of the nested interval theorem used the endpoints of the intervals crucially in the proof. One might wonder if the same theorem holds for open intervals (even though the proof would have to change).
Show the analogous theorem for open intervals is false by finding a counter example: can you find a collection of nested open intervals whose intersection is empty?
Exercise 5.5 Either give an example of each (explaining why your example works) or provide an argument (it doesn’t have to be a formal proof) why no such example should exist:
A sequence of nested closed intervals, whose intersection contains exactly \(n\) points, for some finite \(n>1\).
A sequence of nested closed rays whose intersection is empty. (A closed ray has the form \([a,\infty)\) or \((-\infty,a]\) as in Definition 4.4).
5.4 Working with \(\inf\) and \(\sup\)
Proposition 5.1 (Uniqueness of Supremum) If the supremum of a set exists, it is unique.
Proof. Let \(A\) be a set. To show uniqueness, we will assume that there are two numbers \(x\) and \(y\) which both satisfy the definition of the supremum of \(A\), and then we will show \(x=y\). Thus, any two possibilities for the supremum are equal, so if theres a supremum at all there can only be one.
To prove \(x=y\), we will prove \(x\leq y\) and \(y\leq x\). Once we have these two, we can immediately conclude that since we can’t simultaneously have \(x<y\) and \(y<x\) (what axiom of an ordered field would this violate?) we must have \(x=y\).
If \(x\) and \(y\) both are least upper bounds for \(A\), then they are both in particular upper bounds. So, \(x\) is an upper bound and \(y\) is a least upper bound implies \(y\leq x\). But similarly, \(y\) being an upper bound while \(x\) is a least upper bound implies \(x\leq y\). Thus \(x=y\) and so the supremum is unique.
Remark 5.2. These are two important proof techniques in analysis.
First, one way to show that something is unique is to show that if you had two of them, they have to be equal. Second, to show \(x=y\) it is often useful to show both \(x\leq y\) and \(y\leq x\).
Exercise 5.6 Prove the infimum of a set is unique when it exists.
Proposition 5.2 Let \(A\) be a set which is bounded above. An upper bound \(\alpha\) for \(A\) is actually the supremum if for every positive \(\epsilon>0\), there exists some element of \(A\) greater than \(\alpha-\epsilon\).
Proof. (In the book, Theorem 1.24, page 26) Let’s prove the contrapositive, meaning we assume the conclusion is false and prove the premise is false. The conclusion would be false if there were some positive \(\epsilon\) where no element of \(a\) is larger than \(\alpha-\epsilon\). But this means that \(\alpha-\epsilon\geq a\) for all \(a\in A\), or that \(\alpha-\epsilon\) is an upper bound for \(A\). Since this is less than \(\alpha\) (remember, \(\epsilon\) is positive), we found a smaller upper bound, so \(\alpha\) cannot be the least upper bound: thus its false that \(\alpha = \sup A\).
Since anytime our proposed condition doesn’t hold, \(\alpha\) isnt the supremum, this means if \(\alpha\) were the supremum, the condition must hold! And this is what we sought to prove.
Remark 5.3. The contrapositive is a very useful proof style, especially in situations where the premise is something short, and the conclusion is something complicated. By taking a look at the contrapositive, you get to assume the negation of the conclusion, meaning you get to assume the complicated thing, and then use it to prove the simple thing (the negation of the premise
Exercise 5.7 Prove the corresponding characterization of infima: a lower bound \(\ell\) for a set \(A\) is the infimum if for every positive \(\epsilon>0\) there is some element of \(A\) less than \(\ell + \epsilon\).
Exercise 5.8 Let \(A,B\) be nonempty bounded subsets of a complete field, and suppose \(A\subset B\). Prove that \(\sup A\leq \sup B\).
Exercise 5.9 Let \(A,B\) be subsets of a complete ordered field with \(\sup A<\sup B\).
- Prove that there is an element \(b\in B\) which is an upper bound for \(A\).
- Give an example to show this is not necessarily true if we only assume \(\sup A\leq \sup B\).
Example 5.6 Let \(A\) be a bounded set with supremum \(\sup A\) and \(c\) an element of the field. Define the set \(S = \{a+c\mid a\in A\}\). Then \[\sup S = c+\sup A\]
To prove this, we need to show two things: (1) that \(c+\sup A\) is an upper bound for \(S\), and (2) that its in fact the least upper bound.
First, we consdier (1). Since \(\sup A\) is an upper bound for \(A\), we know \(\forall a\in A, a\leq \sup A\). Adding \(c\) to both sides, we also have \(c+a\leq c+\sup A\) for all \(a\), which implies \(c+\sup A\) is an upper bound.
Now, (2). Let \(u\) be any upper bound for \(S\). This means that \(u \geq c+a\) for all \(a\in A\), so subtracting \(c\) from both sides, that \(u-c\geq a\). Thus, \(u-c\) is an upper bound for \(A\), and this is real progress because we know \(\sup A\) is the least upper bound. That implies \(\sup A\leq u-c\) and so adding \(c\) to both sides, \(c+\sup A\leq u\). Putting this all together, we assumed \(u\) was any upper bound and we proved \(c+\sup A\) was a smaller one.
Thus, \(c+\sup A\) is the least upper bound to \(S\), and so by definition we have \(\sup S = c+\sup A\) as required.
Exercise 5.10 Let \(c>0\) and \(A\) be a bounded set with supremum \(\sup A\). Define the set \(S = \{ca\mid a\in A\}\). Then \(\sup S\) exists and \[\sup S = c\sup A\]
Exercise 5.11 Let \(A,B\) be two bounded nonempty sets. Assuming that the suprema and infima of \(A\) and \(B\) both exist, prove they do for \(A\cup B\) as well and
\[\sup A\cup B = \max\{\sup A, \sup B\}\] \[\inf A \cup B = \min\{\inf A, \inf B\}\]
Exercise 5.12 For each item, compute the supremum and infimum, or explain why they does not exist. (You should explain your answers but you do not need to give a rigorous proof)
- \(A=\left\{\frac{(-1)^n}{n}\mid n\in \NN\right\}\)$
- Fix \(\beta\in (0,1)\), and define \(B=\{\beta^n\mid n\in\NN\}\)
- Fix \(\gamma\in (1,\infty)\) and define \(C=\{\gamma^n\mid n\in\NN\}\).
Exercise 5.13 (Sup and Inf of Intervals) Let \(A,B\) be two open intervals in \(\RR\), and assume that \(\sup A = \inf B\).
True or false: it is possible to add a single point to \(A\cup B\) so the entire set is an interval. (Explain your reasoning, but you don’t have to write a rigorous proof).
5.4.1 \(\bigstar\) Equivalents to Completeness
Here we tackle the natural questions about why we chose suprema to codify completeness in a series of exercises. Our goal at the end of these is to show that the following three possible completeness axioms are all logically equivalent:
- Any nonempty set thats bounded above has a supremum.
- Any nonempty set thats bounded below has an infimum.
- Any nonempty set thats bounded has a supremum and infimum.
Exercise 5.14 For a set \(A\) let \(-A\) denote the set of additive inverses: \(-A=\{-a\mid a\in A\}\). Prove that in a complete field if \(A\) is nonempty and bounded below then \[\sup(-A)=-\inf(A)\]
Thus, assuming that suprema exist forces infima to exist, so in our list above, (1) implies (2).
Exercise 5.15 Prove the converse of the above: if we instead assume that the infimum of every nonempty set thats bounded below exists, show that the supremum of every nonempty set thats bounded above exists.
This shows (2) implies (1), so all together we know that (1) and (2) are equivalent. But since (3) is just the conditions (1) and (2) together, we can derive (3) from either as
\[(1)\implies (1)\textrm{ and }(2) = (3)\] \[(2)\implies (2)\textrm{ and }(1) = (3)\]
Thus both (1) and (2) imply (3). But since (1) and (2) are themselves special cases of (3), we already know (3) implies each of them! So, both of (1) and (2) are equivalent to (3), and all three conditions are logically equivalent to one another.