PG4.4 Supremum, infimum and completeness

Simulate

Check the claim with numbers

Take the set of the numbers $1 - \frac{1}{n}$ for whole numbers $n \ge 1$ : 0, $\frac{1}{2}$ , $\frac{2}{3}$ , $\frac{3}{4}$ , and so on. Every element is below 1. Does the set have a largest element, and what is the smallest number above all of it?

from fractions import Fraction A = [1 - Fraction(1, n) for n in range(1, 100001)] print(max(A), max(A) < 1, min(A)) for eps in [Fraction(1, 10), Fraction(1, 100), Fraction(1, 1000)]: n = next(n for n in range(1, 100001) if 1 - Fraction(1, n) > 1 - eps) print(f"first element above 1 - {float(eps)}: n = {n}")

⌘/Ctrl + Enter runs the cell

Among the first 100,000 elements, the largest is $\frac{99999}{100000}$ , still below 1, and the smallest is 0. Yet every number tried just below 1 is passed: an element exceeds $1 - 0.001$ from $n = 1001$ on. So 1 looks like the smallest number above the set, though no element reaches it.

Some sets have no such number, since nothing lies above all of 1, 2, 3 and so on. And the smallest number above a set need not be a fraction. Bisection (lesson 1.3.2) closes in on the top of the set of $x$ with $x^2 < 2$ :

lo, hi = 1.0, 2.0 # lo is in the set; hi is above all of it for step in range(50): mid = (lo + hi) / 2 if mid * mid < 2: lo = mid else: hi = mid print(lo, hi, 2 ** 0.5, lo * lo < 2, hi * hi >= 2)

⌘/Ctrl + Enter runs the cell

After 50 halvings, lo and hi agree with $\sqrt{2} = 1.4142135623730951$ to about 15 digits. But $\sqrt{2}$ is not a fraction (stage PG2 proves it), so with fractions alone this set would have no smallest number above it. The real numbers fill such gaps, and this lesson says how.

Conjecture

A = \left\{ 1 - \frac{1}{n} : n \ge 1 \right\}

One hundred thousand elements stay below 1, and three numbers just below 1 are passed. A proof must handle every element and every number below 1.

Upper bounds and the supremum

The braces build a set: $A$ is the set of all numbers $1 - \frac{1}{n}$ for whole numbers $n \ge 1$ . An upper bound of a set $A$ is a number $u$ with $a \le u$ for every element $a$ . If $A$ has one, it is bounded above, and then it has many: anything above an upper bound is one too.

The supremum of $A$ , written $\sup A$ , is its least upper bound: an upper bound that is at most every other upper bound. Lower bounds and the infimum $\inf A$ , the greatest lower bound, are the same ideas turned upside down.

Rule: Supremum

\begin{gathered} s = \sup A \text{ means:} \\ a \le s \text{ for every } a \in A, \text{ and} \\ s \le u \text{ for every upper bound } u \end{gathered}

The symbol $\in$ reads "is in". A supremum need not belong to $A$ . When it does, it is the maximum of $A$ , its largest element.

For the set of the conjecture, 2, 1.5 and 1 are upper bounds. But 0.9 is not, because the element $1 - \frac{1}{11}$ is above it: the simulation's first element above $1 - 0.1$ .

The ε-test

The second half of the definition is easier to check in another form. An upper bound $s$ is the supremum exactly when every number below $s$ is passed by some element.

Rule: The ε-test for a supremum

\begin{gathered} \text{an upper bound } s \text{ is } \sup A \text{ when} \\ \text{for every } \varepsilon > 0 \text{ some } a \in A \\ \text{has } a > s - \varepsilon \end{gathered}

The test works both ways: a supremum always passes it, and an upper bound that passes it is the supremum.

Here is why. Suppose the upper bound $s$ passes the test, and $u < s$ . Take $\varepsilon = s - u > 0$ : some element is above $s - \varepsilon = u$ , so $u$ is not an upper bound, and $s$ is the least.

Conversely, let $s = \sup A$ and $\varepsilon > 0$ . Then $s - \varepsilon$ is below the least upper bound, so it is not an upper bound, and some element is above it.

Completeness

Rule: Completeness

\begin{gathered} \text{every non-empty set} \\ \text{of real numbers} \\ \text{with an upper bound} \\ \text{has a supremum} \end{gathered}

We take this as a basic property of the real numbers, as lesson PG3.1 took well-ordering for the whole numbers. The fractions alone lack it, as the set of $x$ with $x^2 < 2$ suggests.

Completeness says a supremum exists without saying what it is. Lesson PG4.5 uses exactly that, to prove that a sequence converges before its limit is known.

Format 2

Fill the gap

The proof of the conjecture, with its key steps left out. Type each missing piece in $n$ , or as a number, then check.

n \ge 1

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

Format 3

Find the error

A proof that every non-empty set with an upper bound has a largest element. The claim is false, so some line must be wrong. Select it.

Simulate

A claim of your own to prove

Lesson PG4.1 chose each $N$ with the Archimedean property: for every real number $x$ there is a whole number $n > x$ . For any particular $x$ , Python finds one with math.floor, which rounds down to a whole number.

import math from fractions import Fraction for x in [Fraction(5, 2), Fraction(10**6) + Fraction(1, 2), Fraction(10**15) + Fraction(3, 10)]: n = math.floor(x) + 1 print(x, n, n > x) for eps in [Fraction(1, 10), Fraction(1, 10**6)]: n = math.floor(1 / eps) + 1 print(eps, n, Fraction(1, n) < eps)

⌘/Ctrl + Enter runs the cell

Even for $x$ just above $10^{15}$ , the whole number 1000000000000001 is larger. In the form lesson PG4.1 used: for $\varepsilon = 10^{-6}$ , $n = 1000001$ has $\frac{1}{n} < \varepsilon$ .

Conjecture

x

Python finds a whole number above each $x$ it is given. The claim is that one exists for every real number, and its proof needs completeness.

Format 4

Write it

Prove the Archimedean property from completeness. Argue by contradiction: suppose that some real number $x$ has $n \le x$ for every whole number $n$ .

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

The form lesson PG4.1 used follows at once. For $\varepsilon > 0$ , take a whole number $n > \frac{1}{\varepsilon}$ ; then $\frac{1}{n} < \varepsilon$ .

u

Supremum, infimum and completeness

Check the claim with numbers

Upper bounds and the supremum

Rule: Supremum

The ε-test

Rule: The ε-test for a supremum

Completeness

Rule: Completeness

Fill the gap

Find the error

A claim of your own to prove

Write it

Summary card

Free further reading