Completeness and the Supremum
1. Defining Suprema and Infima
Definition
Given a nonempty set \(E \subset {\mathbb R}\),
- We say that \(E\) is bounded above when there is some real number \(M\) such that \(x \leq M\) for all \(x \in E\). Any number \(M\) of this sort will be called an upper bound of \(E\).
- We say that \(E\) is bounded below when there is some real number \(N\) such that \(x \geq N\) for all \(x \in E\). Any number \(N\) of this sort will be called a lower bound of \(E\).
- We say that \(E\) is bounded when it is bounded above and below.
We take as an axiom that the real numbers have the least upper bound property:
Definition
Every nonempty set \(E\) which is bounded above has a least upper bound which will be called the supremum of \(E\) and written \(\sup E\). The supremum of \(E\) is characterized by its two fundamental properties:
- (It bounds) For all \(x \in E\), \(x \leq \sup E\).
- (It's least) For all upper bounds \(M\) of \(E\), \(\sup E \leq M\).
Important
It is extremely important to observe that the inequalities are less than or equal to—they are not strict inequalities.
Note that these properties uniquely specify the value of the supremum: suppose for a nonempty set \(E\) which is bounded above that \(a\) and \(b\) are two real numbers such that \(x \leq a\) and \(x \leq b\) for all \(x \in E\) and \(a \leq M\), \(b \leq M\) for all upper bounds \(M\) of \(E\). Since \(a\) is an upper bound and \(b\) dominates all upper bounds, \(a \leq b\). But also \(b\) is an upper bound and \(a\) dominates all upper bounds, so \(b \leq a\). By the order trichotomy, this forces \(a = b\). This means that any process you follow that provably produces a number satisfying both parts of the least upper bound property will be guaranteed to correctly yield the supremum.
Important
If a nonempty set \(E\) is not bounded above, we sometimes say that the supremum of \(E\) is infinite and write \(\sup E = \infty\). This should not be regarded as a deep insight about infinity, but rather as just a way of using symbols on a page as shorthand for a more precise statement. For now, \(\infty\) is just a shorthand notation and not a thing in and of itself. Similarly, a nonempty set \(E\) which is not bounded below will sometimes be indicated by writing \(\inf E = -\infty\).
There is also a completely symmetric notion of the greatest lower bound property. A nonempty set \(E\) which is bounded below has an infimum, denoted \(\inf E\) which is a lower bound for \(E\) and is greater than or equal to all lower bounds \(N\) of \(E\). The existence of the infimum does not formally need to be an axiom—the existence of the supremum forces the existence of the infimum as well.
Theorem
For every set \(E\) which is bounded below, there is a real number \(\inf E\) such that \(x \geq \inf E\) for all \(x \in E\) and \(N \geq \inf E\) for all lower bounds \(N\) of \(E\).
Proof
Consider the set \(-E := \{ x \in {\mathbb R} \ : \ -x \in E\}\). This set is Nonempty because \(E\) has some element \(x\), meaning that \(-x \in -E\). The set \(-E\) is bounded above because if \(N\) is a lower bound for \(E\), then \(y \in -E\) means \(y = -x\) for some \(x \in E\), so \(-x \leq -N\). Thus \(-N\) is an upper bound for \(-E\). Thus \(-E\) has a supremum. We claim that \(-\sup (-E)\) is a greatest lower bound of \(E\). First, note that since \(y \leq \sup(-E)\) for all \(y \in -E\), \(-y \geq -\sup(-E)\). But every \(x \in E\) equals \(-y\) for some \(y \in -E\). Likewise, if \(N\) is a lower bound of \(E\), then \(-N\) is an upper bound of \(-E\), so \(\sup (-E) \leq -N\), giving \(N \leq - \sup(-E)\).
2. Examples
Example
- The supremum of the set \(\{1,2,3\}\) is \(3\) and the infimum is \(1\). Note that the supremum and infimum are actual elements of the set.
- The supremum of the set \(\{x \in {\mathbb R} \ : \ 0 < x < 1\}\) is \(1\) and the infimum is zero. Note that neither \(0\) nor \(1\) are actual elements of the set. To see why \(1\) is the supremum, note that \(1\) is an upper bound by definition. If \(M\) were any upper bound of the set, it would have to be positive because \(\frac{1}{2}\) belongs to the set. If it were the case that \(M <1\), then \((M+1)/2\) would be a positive number less than one also, meaning that \((M+1)/2\) would belong to the set. That would be a problem because \((M+1)/2 > M\), contradicting the fact that \(M\) is an upper bound. Thus \(M \geq 1\).
- For any nonempty set \(E\) which is bounded, it is always the case that \(\inf E \leq \sup E\) simply because there's an element \(x \in E\) and we know that \(\inf E \leq x\) and \(x \leq \sup E\). The supremum and infimum would be equal if and only if \(E\) has only one element.
3. Suprema, Infima, and \(\epsilon\) Approximation
The notion of supremum (and similarly infimum) has within it the seeds of the fundamental calculus concepts. The reason for this is that, while the supremum may not actually belong to the set, it must be “arbitrarily close” to points belonging to the set. This idea is made precise in the lemma below. The analogous result for the infimum can be obtained by multiplying everything by \(-1\) as usual.
Lemma
Given a nonempty set \(E\) which is bounded above, the supremum \(\sup E\) is the unique real number having both of the following properties:
- For each \(x \in E\), \(x \leq \sup E\).
- For any \(\epsilon > 0\), there is some \(x \in E\) such that \(x > \sup E - \epsilon\).
Proof
First, suppose there were two numbers \(a,b \in R\) such that \(x \leq a\) and \(x \leq b\) for all \(x \in E\) and that every \(\epsilon > 0\) gave the existence of some \(x \in E\) such that \(x > a - \epsilon\) and likewise some \(x' > b - \epsilon\). If \(a \neq b\), then either \(a < b\) or \(b > a\); switching the names if necessary, we may assume that \(a\) is smaller, i.e., \(a < b\). Now let \(\epsilon = b - a\). We know there exists \(x' \in E\) such that \(x > b - \epsilon = a\). But by order trichotomy, this violates the requirement that \(x' \leq a\) for all \(x' \in E\). So it must not be true that \(a < b\), and consequently we would have to have \(a = b\).
Now we show that \(\sup E\) itself does have the desired properties. First, because \(\sup E\) is an upper bound, it is necessarily the case that \(x \leq \sup E\) for all \(x \in E\). Now suppose the second property failed, i.e., that there were some \(\epsilon > 0\) for which no \(x \in E\) had \(x > \sup E - \epsilon\). This would mean that \(x \leq \sup E - \epsilon\) for all \(x \in E\), and hence \(\sup E - \epsilon\) would be an upper bound. But it is strictly smaller than \(\sup E\), so it would contradict the fact that the supremum is the least upper bound. Thus consistency demands that the second property must always be true.
Corollary (Natural Number-Like Sets)
Suppose that \(E \subset {\mathbb R}\) is nonempty and has the property that for any \(x \in E\), there is some \(x' \in E\) with \(x' \geq x + 1\). Then \(E\) is not bounded above, i.e., \(\sup E = \infty\). Since \(E\) has no upper bound, it must be the case that for any real number \(r\), there is some \(x \in E\) such that \(r < x\).
In particular, the natural numbers (which will be studied more carefully later) must be unbounded because they are closed under the operation of adding \(1\). This means that for every real number \(r\), there is some natural number \(N \in \mathbb{N}\) such that \(r < N\).
Proof
If \(E\) were bounded above, it would have a supremum, and there would be some \(x \in E\) such that \(\sup E - \frac{1}{2} < x \leq \sup E\). But then by definition of \(E\), there would be an \(x' \in E\) with \(x' \geq x+1\). This would mean that \(x' \geq x + 1 > \sup E - \frac{1}{2} + 1 > \sup E\), which cannot happen because \(x' \in E\), so \(x' \leq \sup E\) by definition of the supremum. Since \(E\) cannot have a supremum, it must be unbounded.
Since \(r \in {\mathbb R}\) is not an upper bound, there must be some \(x \in E\) which is too large, i.e., \(x > r\).
Corollary (Integer-Like Sets)
Suppose that \(E \subset {\mathbb R}\) is nonempty, is not bounded below, and has the property that for any \(x \in E\), there is some \(x' \in E\) such that \(x + \frac{1}{2} < x' \leq x+1\). Then for any \(a,b \in {\mathbb R}\) with \(b > a+1\), there is an \(x \in E \cap (a,b)\).
In particular, since we will see that the integers \(\mathbb{Z}\) have this property, it will follow that every open interval \((a,b)\) of length (i.e., \(b-a\)) greater than \(1\) must contain an integer.
Proof
We know there is some \(x \in E\) because it's nonempty. If \(x \in (a,b)\), we're done. So assume that either \(x \leq a\) or \(x \geq b\). Because \(E\) is bounded below, we may assume that there is some \(x < b\), so without loss of generality, we may also assume that there is some \(x \in E\) such that \(x \leq a\).
The set \(S := \{ x \in E \ : \ x \leq a\}\) is nonempty and by definition bounded above by \(a\). It must have a supremum which is less than or equal to \(a\). But also there must be an element \(x \in S\) such that \(x > \sup S - \frac{1}{2}\). By definition of \(E\), there must be \(x' \in E\) such that \(x + \frac{1}{2} < x' \leq x+1\). This would mean that \(\sup S < x' \leq x + 1 \leq \sup S + 1 \leq a + 1\). Since \(x' > \sup S\), \(x'\) cannot belong to \(S\), meaning that \(x' > a\). So \(a < x' \leq a+1 < b\), meaning that \(x'\) is in \(E \cap (a,b)\).
4. The Archimedean Principle
The first fundamental result which can be proved using the toolbox of supremum and infimum is the Archimedean Principle, which asserts in its purest form that there are no pairs of positive real numbers \(x\) and \(y\) such that \(x + \cdots + x < y\) for all repeated sums of \(x\) involving any number of terms. In other words, if \(x\) and \(y\) are both positive, then there must be some natural number for which \(n x \geq y\). This generalizes to the familiar statement that every interval must contain a rational number.
Theorem (Archimedean Principle)
Suppose that \(N\) is a set of positive real numbers satisfying the property above of being natural number-like. Suppose that \(Z\) is a set of real numbers satisfying the property above of being integer-like. Let \(Q\) be the set of all real numbers expressible as \(z/n\) for some \(n \in N\) and some \(z \in Z\). Then for any unequal real numbers \(x\) and \(y\), there is some \(q \in Q\) strictly between \(x\) and \(y\).
Proof
Without loss of generality, we may assume that \(x\) is the smaller of the two among \(x\) and \(y\). Show that there is some \(n \in N\) such that the length of \((nx,ny)\) is strictly greater than \(1\). This would force the existence of some \(z \in Z\) inside \((nx,ny)\), and then dividing by \(n\) (which is positive) would give \(z/n \in (x,y)\).
Prove the existence of this \(n\) by contradiction: if it did not exist, then \(n(y-x) \leq 1\) for all \(n \in N\). That would mean that \(n \leq (y-x)^{-1}\) for all \(n\), which violates the conclusion that \(N\) has no upper bound.