$$$$

3  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 $\mathbb{Q}$, 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.

3.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 3.1 (Nested Intervals) A sequence of intervals $I_1,I_2,I_3,\dots$ 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 number that could be captured after infinitely many steps. We capture this unstated assumption rigorously below, and title it the Approximation Property based on its use approximating numbers by intervals:

Definition 3.2 (Approximation Property) A number system has the approximation property if the intersection of any sequence of nested intervals whose lengths go to zero contains a single element.

How do we tell if our current axioms imply that our number system has the approximation property? 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.

Theorem 3.1 The axioms of an ordered field are not enough to deal with completed infinity: there are ordered fields in which do not have the approximation property.

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. One might be tempted to just take the approximation property itself as an axiom(!); but this comes with its own challenges. The property is rather specific (about certain collections nested intervals), whereas we want axioms to be as general and simple-to-state as possible, and worse, it contains a currently undefined term lengths tending to zero which we would have to first make rigorous.

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.

3.2 Suprema and Infima

A confidence interval like $[{\text{width}}_n,{\text{height}}_n]$ or $[{\text{inscribed}}_n,{\text{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 3.3 (Bounds) Let $S$ be a nonempty subset of an ordered field. An upper bound for $S$ is an element $u\in \mathbb{F}$ greater than or equal to all the elements of $S$: $$\mathrm{\forall }s\in Ss\le u$$ A lower bound for $S$ is an element $\ell \in \mathbb{F}$ which is less than or equal to all the elements of $S$: $$\mathrm{\forall }s\in S\ell \le 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 3.4 (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 3.5 (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 \le u$.

When such a least upper bound exists, we call it the supremum of $S$ and denote it $\sigma =supS$.

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 3.1 (A set with no maximum) The set $(0,1)=\{x\in \mathbb{Q}\mid 0<x<1\}$ has no maximal element, but it does have a supremum in $\mathbb{Q}$, namely $1=supS$.

Definition 3.6 (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 \le \lambda$.

If such an element exists it is denoted $\lambda =infS$.

Example 3.2  

• The set $\mathbb{N}$ has no upper bounds at all, so $sup\mathbb{N}$ does not exist. It has many lower bounds (like 0, and -14), and its infimum is $inf\mathbb{N}=1$.

• The rational numbers themselves have no upper nor lower bound, so $sup\mathbb{Q}$ and $inf\mathbb{Q}$ do not exist.

3.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 3.7 (Completeness) An ordered set is complete if every nonempty subset $S$ that is bounded above has a supremum.

Remark 3.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 3.2 ($\mathbb{Q}$ is not complete) The set $S=\{s\in \mathbb{Q}\mid s^2<2\}$ does not have a supremum in $\mathbb{Q}$.

Proof (Sketch). A rigorous proof can be given by contradiction: assume that a supremum $\sigma =supS$ 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 4.1 and Exercise 4.2).

Once its known that the supremum must satisfy ${\sigma }^2=2$, we apply Pythagoras’ observation (Theorem 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 3.3 (Nested Interval Property) Let $\mathbb{F}$ be an ordered field which is also complete, and $I_0,I_1,I_2,\dots ,I_n,\dots$ be a collection of nested closed intervals. Then their intersection is nonempty: $$\bigcap _{n\ge 0}{I}_n\ne \varnothing$$

Proof. Let $I_n=[a_n,b_n]$. We need to use the fact that $\mathbb{F}$ 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,\dots ,a_n,\dots \}$$ 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 =supA$. 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\le \alpha$. But $b_n$ is an upper bound for $A$ so the least upper bound must satisfy $\alpha \le b_n$. Putting these together $$a_n\le \alpha \le b_n⟹\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.

Confirm that the property the ancients assumed held of the number line is now a theorem of our formal system!

Exercise 3.1 (The Approximation Property) Let $I_n=[a_n,b_n]$ be a nested sequence of intervals and assume $sup\{a_n\}=inf\{b_n\}$. Then show $\bigcap _n{I}_n$ contains exactly one point.

3.4 Working with $inf$ and $sup$

Proposition 3.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\le y$ and $y\le 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\le x$. But similarly, $y$ being an upper bound while $x$ is a least upper bound implies $x\le y$. Thus $x=y$ and so the supremum is unique.

This uses 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\le y$ and $y\le x$.

Exercise 3.2 Prove the infimum of a set is unique when it exists.

Proposition 3.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. 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 \ge 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 =supA$.

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 3.2. 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 3.3 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 3.4 Let $A,B$ be nonempty bounded subsets of a complete field, and suppose $A\subset B$. Prove that $supA\le supB$.

Example 3.3 Let $A$ be a bounded set with supremum $supA$ and $c$ an element of the field. Define the set $S=\{a+c\mid a\in A\}$. Then $$supS=c+supA$$

To prove this, we need to show two things: (1) that $c+supA$ is an upper bound for $S$, and (2) that its in fact the least upper bound.

First, we consider (1). Since $supA$ is an upper bound for $A$, we know $\mathrm{\forall }a\in A,a\le supA$. Adding $c$ to both sides, we also have $c+a\le c+supA$ for all $a$, which implies $c+supA$ is an upper bound.

Now, (2). Let $u$ be any upper bound for $S$. This means that $u\ge c+a$ for all $a\in A$, so subtracting $c$ from both sides, that $u-c\ge a$. Thus, $u-c$ is an upper bound for $A$, and this is real progress because we know $supA$ is the least upper bound. That implies $supA\le u-c$ and so adding $c$ to both sides, $c+supA\le u$. Putting this all together, we assumed $u$ was any upper bound and we proved $c+supA$ was a smaller one.

Thus, $c+supA$ is the least upper bound to $S$, and so by definition we have $supS=c+supA$ as required.

Exercise 3.5 Let $c>0$ and $A$ be a bounded set with supremum $supA$. Define the set $S=\{ca\mid a\in A\}$. Then $supS$ exists and $$supS=csupA$$

Exercise 3.6 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

$$supA\cup B=max\{supA,supB\}$$ $$infA\cup B=min\{infA,infB\}$$

Exercise 3.7 (Sup and Inf of Intervals) Let $A,B$ be two open intervals in $\mathbb{R}$, and assume that $supA=infB$.

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).

3.5 Problems

Exercise 3.8 Let $A,B$ be subsets of a complete ordered field with $supA<supB$.

• 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 $supA\le supB$.

Exercise 3.9 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 \mathbb{N}\}$
• $\{x\mid 1+\frac{(-1{)}^n}{n},n\in \mathbb{N}\}$

Exercise 3.10 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=\{\frac{(-1{)}^n}{n}\mid n\in \mathbb{N}\}$$
• Fix $\beta \in (0,1)$, and define $B=\{{\beta }^n\mid n\in \mathbb{N}\}$
• Fix $\gamma \in (1,\mathrm{\infty })$ and define $C=\{{\gamma }^n\mid n\in \mathbb{N}\}$.

Exercise 3.11 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 3.12 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,\mathrm{\infty })$ or $(-\mathrm{\infty },a]$ as in ?def-intervals).

3.5.1 $★$ 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:

• 1. Any nonempty set thats bounded above has a supremum.
• 2. Any nonempty set thats bounded below has an infimum.
• 3. Any nonempty set thats bounded has a supremum and infimum.

Exercise 3.13 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 3.14 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)⟹(1)\text{ and }(2)=(3)$$ $$(2)⟹(2)\text{ 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.