Metric Spaces, Least Upper Bound

Least Upper Bound

Let S be a set of real numbers, bounded above by the real number b. There is a smallest real number u that bounds all of S. Most books call this an axiom, the beginning of "real analysis", but it is actually a theorem if real numbers are defined properly. We'll prove the existence of the greatest lower bound. You can multiply through by -1 to find the least upper bound.

Let b be a real number that is less than or equal to every number in the set S, and let q be any point in S. Rescale, so that b is 0 and q is 1. Now all of S is bounded below by 0, and at least one point in S is as high as 1. Build a binary number t as follows.

Let t₀ = 0. If 1/2 is a lower bound for all of S, let t₁ = 1/2, else let t₁ = 0. Next let r = 1/4 and let t₂ = t₁+r if this continues to bound all of S, otherwise let t₂ = t₁. Divide r by 2, giving 1/8, and let t₃ = t₂+r if this bounds all of S, otherwise let t₃ = t₂. Continue this process, building the infinite sequence t. Note that t is a binary expansion, like our earlier decimal expansions, but in base 2. Thus t is also a real number. We don't have to worry about an infinite tail of ones, such as 0.11011111…, because t, by its construction, would have produced 0.11100000…

Suppose some point q in S is less than t. Write q in binary, avoiding the infinite tail of ones. Note the first digit where q and t differ. We must have q_j = 0 and t_j = 1. However, t would not have set t_j to 1, because that rational number exceeds q.

Now suppose a larger number q is still a lower bound for S. Write q in binary as before, and suppose t_j = 0 and q_j = 1. At the j^th step, t_j would be set to 1, because that rational approximation still bounds all of S. Therefore t is the greatest lower bound for S.