1.1 The real numbers and completeness

The rational numbers have holes, like the one where the square root of 2 should be. The real numbers are the rationals with every hole filled, and the precise way to say "no holes" is that every bounded set has a least upper bound. All of calculus rests on this one property.

In school, “the real numbers” meant all the numbers on the number line. That picture hides the one property every theorem of calculus needs. The rational numbers (fractions of whole numbers) also sit on the line, densely: between any two there is another. Yet they have holes, and calculus does not work on them. This chapter says exactly what a hole is, what it means to have none, and proves the first consequences. It also introduces the move that appears in nearly every analysis proof: “for every $\varepsilon > 0$ , there is an element within $\varepsilon$ of the supremum.” Here $\varepsilon$ (the Greek letter epsilon) is the name for a small positive number that somebody else picks, and your job is to answer whatever they pick.

Before you start

Chapter 0.1 (quantifiers and negation) and 0.2 (proof by contradiction, and the irrationality of $\sqrt 2$ ).

Quick checkWhich is the negation of '

M

is an upper bound of

S

', where that means

\forall x \in S:\ x \le M

Quick checkWhy is

\sqrt 2

not a fraction?

The picture: a hole in the rationals

Take all positive rationals whose square is less than 2:

A = \{ q \in \mathbb Q : q > 0,\ q^2 < 2 \}.

It contains $1$ , $1.4$ , $1.41$ , $1.414$ , … creeping up towards $\sqrt 2$ . Every element is less than $1.5$ (if $q \ge 1.5$ then $q^2 \ge 2.25$ ), so $A$ is bounded above. Is there a smallest rational number that is $\ge$ every element of $A$ ? Try one: $1.5$ works but $1.42$ is smaller and still works ( $1.42^2 = 2.0164 > 2$ ); $1.415$ is smaller still. Any rational upper bound can be beaten by a smaller rational upper bound, because the “right” answer, $\sqrt 2$ , is missing from $\mathbb Q$ . The set “wants” a least upper bound and the rationals cannot provide one. That missing point is a hole. A later example proves this carefully; first, here is a way to see the beating-by-a-smaller-bound move in numbers.

Your answerYou hold the rational upper bound

M = 1.5

A

. The number

\frac M2 + \frac1M

is a smaller rational upper bound (this is the Babylonian step you will meet in 1.2). Compute it, as a fraction.

Why· Why holes break calculus

The function $f(x) = x^2 - 2$ is negative at $x = 1$ and positive at $x = 2$ . In school, the intermediate value theorem then gave a root between them. But if you only allow rational $x$ , there is no root: $x^2 = 2$ has no rational solution. So a fact as basic as “a continuous curve that goes from below zero to above zero must cross zero” is FALSE over the rationals. Whatever makes it true over the reals must be a property the rationals lack. That property is completeness.

Where this came from· Filling the holes, 1872

The Greeks knew $\sqrt 2$ is not a ratio of whole numbers. For about two thousand years mathematicians used irrational numbers without saying what they were. Calculus was built on them in the 1600s and 1700s, still without a definition. In 1858 Richard Dedekind had to teach differential calculus for the first time, at the Zurich Polytechnic. He was unhappy that its basic theorems, such as “a bounded increasing sequence has a limit”, were justified by geometric intuition. In 1872 he published his answer: a real number is a “cut” splitting the rationals into a lower and an upper part. In the same year Georg Cantor, who came to the question through the study of trigonometric series, defined real numbers through sequences of rationals that bunch together. Both constructions produce a number system with the property this chapter calls completeness.

Definitions and theorems

Bounds

Definition B

Upper bound

A real number $M$ is an upper bound of a set $S$ of real numbers if $x \le M$ for every $x \in S$ . A lower bound is defined the same way with $x \ge m$ .

In one line $M$ is an upper bound of $S$ if every element of $S$ is at most $M$ .

Why it existsTo talk about the 'top' of a set that has no largest element, we first need numbers that sit above all of it.

Definition B

Bounded

$S$ is bounded above if it has at least one upper bound, bounded below if it has a lower bound, and bounded if it is both.

In one lineA set is bounded above if it has an upper bound, bounded below if it has a lower bound, and bounded if both.

Why it existsCompleteness is a statement about bounded sets.

Definition B

Supremum

A number $s$ is the supremum (or least upper bound) of $S$ , written $s = \sup S$ , if:

$s$ is an upper bound of $S$ , and
if $M$ is any upper bound of $S$ , then $s \le M$ .

In one lineThe supremum of $S$ is its least upper bound: an upper bound that is smaller than every other upper bound.

Why it existsIt is the precise 'top edge' of a set, even when the set has no largest element.

Definition B

Infimum

The infimum $\inf S$ is the greatest lower bound: a lower bound $m$ with $m \ge$ every other lower bound.

In one lineThe infimum of $S$ is its greatest lower bound.

Why it existsThe bottom edge of a set, the mirror image of the supremum.

Worked example

Find

\sup S

and

\inf S

for

S = \{1 - \frac1n : n = 1, 2, 3, \dots\}

Solution.

List some elements. $S = \{0, \tfrac12, \tfrac23, \tfrac34, \dots\}$ . Concrete elements show the pattern before any proof.
Guess. The elements climb towards 1 and never reach it; the smallest is 0. Guess $\sup S = 1$ and $\inf S = 0$ . Scratch work: guess first, prove after.
1 is an upper bound. $1 - \frac1n < 1$ for every $n$ , since $\frac1n > 0$ . Condition 1 of the definition.
No smaller upper bound. Let $M < 1$ be any number below 1. Then $1 - M$ is a positive number, so choose $n$ with $\frac1n < 1 - M$ . Then $1 - \frac1n > M$ , so $M$ is not an upper bound. Condition 2 of the definition, in its contrapositive form: anything below 1 fails to be an upper bound. Choosing such an $n$ is possible because $\frac1n$ can be made as small as we like. That is the Archimedean property, proved later in this chapter; here we use it before proving it.
The infimum. $0 \in S$ and every element is $\ge 0$ , so 0 is a lower bound that belongs to $S$ . Any lower bound $m$ is at most the element $0$ , so $m \le 0$ . The greatest lower bound is a lower bound that is at least every other lower bound. If a lower bound is itself an element, every lower bound is below it, so it is the infimum.

Answer. $\sup S = 1$ (not in $S$ ) and $\inf S = 0$ (in $S$ ). The supremum need not belong to the set; when it does, it is the set’s maximum.

Quick checkWhich of these sets has a supremum but no largest element?

Your answerLet

S = \{1 - \frac1n : n = 1, 2, 3, \dots\}

. Someone names the tolerance

\varepsilon = 0.001

. What is the smallest

n

for which the element

1 - \frac1n

is above

1 - \varepsilon

The completeness axiom

Definition B

Completeness axiom

Completeness axiom (least-upper-bound property). Every non-empty set of real numbers that is bounded above has a least upper bound in $\mathbb R$ .

In one lineEvery non-empty set of real numbers that is bounded above has a supremum in $\mathbb R$ .

Why it existsIt is exactly the 'no holes' property: the rationals fail it and the reals satisfy it, and every big theorem of calculus depends on it.

The real numbers are the number system satisfying the usual rules of arithmetic and order (the axioms of an ordered field: the algebra you have always done, plus “if $a < b$ then $a + c < b + c$ ” and “if $a < b$ and $c > 0$ then $ac < bc$ ”) and the completeness axiom. The rationals satisfy all the arithmetic and order rules, and fail completeness: the set $A$ in the picture is non-empty and bounded above, but has no least upper bound in $\mathbb Q$ . The example below proves that last claim, and the same idea later builds $\sqrt 2$ inside $\mathbb R$ .

Worked example Rudin Example 1.1 (shortened)

Show that

A = \{q \in \mathbb Q : q > 0,\ q^2 < 2\}

has no least upper bound in

\mathbb Q

Solution. The plan: take any rational upper bound $M$ and produce a smaller rational upper bound. Then no rational upper bound is the least one.

Start with a rational upper bound. Let $M \in \mathbb Q$ , $M > 0$ , with $x \le M$ for all $x \in A$ . We must show an arbitrary upper bound can be beaten, so we assume nothing else about it.
The square of $M$ must be above 2. First, $M^2 \ne 2$ , because $\sqrt 2$ is not rational (the proof in 0.2). Second, $M^2 < 2$ is impossible. In that case put $h = \dfrac{2 - M^2}{2M + 2}$ , a rational number with $0 < h < 1$ (the top is below 2 and the bottom is above 2), and look at $M + h$ : $(M + h)^2 = M^2 + 2Mh + h^2 < M^2 + (2M + 1)h < M^2 + (2M + 2)h = 2$ . So $M + h$ is a rational element of $A$ that is bigger than $M$ , and $M$ was not an upper bound. So $M^2 > 2$ . We use $h^2 < h$ for $0 < h < 1$ . The number $h$ is chosen so that $(2M + 2)h$ is exactly the room left, $2 - M^2$ .
Define a new number. $M' = \dfrac{M}{2} + \dfrac1M = \dfrac{M^2 + 2}{2M}$ . This is rational, because $M$ is. Where it comes from: if $M$ is a little too big, then $\frac2M$ is a little too small (their product is 2), and the average of the two is closer to $\sqrt 2$ than either. This is the number you computed in the check above.
$M'$ is smaller than $M$ . $M - M' = \dfrac{M}{2} - \dfrac1M = \dfrac{M^2 - 2}{2M} > 0$ , since $M^2 > 2$ and $M > 0$ . Common denominator $2M$ , then use $M^2 > 2$ .
$M'$ is still an upper bound. $M'^2 - 2 = \dfrac{(M^2 + 2)^2 - 8M^2}{4M^2} = \dfrac{(M^2 - 2)^2}{4M^2} > 0$ , so $M'^2 > 2$ . Every $x \in A$ has $x^2 < 2 < M'^2$ and $x, M' > 0$ , so $x < M'$ . If $x \ge M'$ then $x^2 \ge M'^2 > 2$ , which contradicts $x \in A$ . The numerator expands as $M^4 + 4M^2 + 4 - 8M^2 = (M^2-2)^2$ .

Answer. Every rational upper bound $M$ of $A$ is beaten by the smaller rational upper bound $M'$ , so $A$ has no least upper bound in $\mathbb Q$ . That is the hole. $\blacksquare$

Beyond the course: for understanding· Is this an axiom or a theorem?

In this book, as in Abbott and Spivak, completeness is taken as an axiom about $\mathbb R$ . In Rudin, and in MATH 521, $\mathbb R$ is first constructed from $\mathbb Q$ (with Dedekind cuts), and completeness is then proved as a theorem. Both approaches give the same number system; the axiomatic one gets to the analysis faster.

The most-used fact about suprema

Every analysis proof that involves a supremum uses the next fact. It turns “least upper bound” into something you can work with: there are elements of $S$ as close to $\sup S$ as you like.

Numbers first. Take $S = \{1 - \frac1n\}$ , so $s = \sup S = 1$ . Somebody names a tolerance $\varepsilon$ , and you must find an element of $S$ in the strip between $1 - \varepsilon$ and $1$ .

Tolerance $\varepsilon$	Strip	An element in the strip	How you found it
$0.1$	$(0.9,\ 1]$	$1 - \frac1{11} \approx 0.909$	need $\frac1n < 0.1$ , so $n = 11$
$0.01$	$(0.99,\ 1]$	$1 - \frac1{101} \approx 0.990099$	need $\frac1n < 0.01$ , so $n = 101$
any $\varepsilon$	$(1 - \varepsilon,\ 1]$	$1 - \frac1n$	pick $n > \frac1\varepsilon$

The tolerance is chosen first, by somebody else, and may be tiny. Then you produce one element. You are not claiming every element is in the strip, only that the strip is never empty.

Theorem B Abbott Lemma 1.3.8

Approximation property of the supremum

Let $s$ be an upper bound of a non-empty set $S$ . Then $s = \sup S$ if and only if for every $\varepsilon > 0$ there is an $x \in S$ with $x > s - \varepsilon$ .

In one lineIf $s = \sup S$ , then for every $\varepsilon > 0$ there is an $x \in S$ with $s - \varepsilon < x \le s$ .

Why it is trueAnything smaller than $s$ , such as $s - \varepsilon$ , is not an upper bound, so some element of $S$ lies above it.

Why· The picture behind the proof

Draw $S$ on the number line with $s$ at its top edge. Slide a marker down from $s$ by any amount $\varepsilon$ . If no element of $S$ were above the marker, the marker would be an upper bound smaller than $s$ , which is impossible if $s$ is the LEAST upper bound. So the strip between $s - \varepsilon$ and $s$ always catches an element of $S$ , however thin you make it. In the table above, the marker at $0.9$ is not an upper bound of $S$ , because $0.909$ is above it.

ProofAbbott 1.3.8

The idea: (⇒) s − ε is smaller than the least upper bound, so it is not an upper bound, and not being an upper bound means some element is above it. (⇐) If some upper bound M were smaller than s, take ε = s − M and get an element above M.

(

\Rightarrow

) Suppose

s = \sup S

, and let

\varepsilon > 0

Two directions. Start with:

s

is the supremum.

Then

s - \varepsilon < s

, so

s - \varepsilon

is not an upper bound of

S

s

is the least upper bound, and

s - \varepsilon

is smaller than

s

So there is an

x \in S

with

x > s - \varepsilon

The negation of 'is an upper bound' (

\forall x \in S:\ x \le M

) is

\exists x \in S:\ x > M

.This is the first quiz of the chapter, used for real.

(

\Leftarrow

) Suppose the condition holds, and let

M

be any upper bound of

S

. We show

s \le M

Other direction: assume the

\varepsilon

condition, and show no upper bound is smaller than

s

Suppose instead

M < s

. Set

\varepsilon = s - M > 0

Proof by contradiction: assume the opposite.

There is

x \in S

with

x > s - \varepsilon = M

Apply the condition with this

\varepsilon

; note

s - \varepsilon = M

M

is not an upper bound, a contradiction. Hence

s \le M

, and

s = \sup S

\blacksquare

That contradicts

M

being an upper bound.

Proof workshopRebuild the (⇒) direction

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

First consequences

Definition B

Archimedean property

The Archimedean property: for every real $x$ there is a natural number $n$ with $n > x$ . Equivalently, for every $\varepsilon > 0$ there is $n$ with $\frac1n < \varepsilon$ .

In one lineFor every real number $x$ there is a natural number $n$ with $n > x$ ; equivalently, $\frac1n$ can be made smaller than any positive number.

Why it existsIt rules out 'infinitely large' and 'infinitely small' real numbers, and it is what makes $\frac1n \to 0$ true.

Why the two forms say the same thing. Given $\varepsilon > 0$ , apply the first form to $x = \frac1\varepsilon$ to get $n > \frac1\varepsilon$ , and then $\frac1n < \varepsilon$ (flip both sides, which is allowed because both are positive). This is the form you will use for $\varepsilon$ -proofs: it is how you turn a tolerance into a whole number $n$ .

Your answerBy the Archimedean property, for

\varepsilon = 0.007

some

n

has

\frac1n < \varepsilon

. What is the smallest whole number

n

that works?

Theorem B Abbott Thm 1.4.2

The reals are Archimedean

The set $\mathbb N = \{1, 2, 3, \dots\}$ is not bounded above in $\mathbb R$ . So for every real $x$ there is $n \in \mathbb N$ with $n > x$ .

In one lineThe natural numbers are not bounded above in $\mathbb R$ .

Why it is trueIf they were, their supremum s would have a natural number above s − 1, and adding 1 would beat s.

ProofAbbott 1.4.2

The idea: If ℕ were bounded above it would have a supremum s (completeness). The approximation property with ε = 1 gives a natural number n > s − 1, and then n + 1 > s is a natural number above the supremum.

Suppose

\mathbb N

is bounded above.

Proof by contradiction.

Then

s = \sup \mathbb N

exists.

\mathbb N

is non-empty and bounded above, so the completeness axiom applies.

There is

n \in \mathbb N

with

n > s - 1

Approximation property with

\varepsilon = 1

Then

n + 1 > s

Add 1 to both sides.

This contradicts

s

being an upper bound of

\mathbb N

. So

\mathbb N

is not bounded above.

\blacksquare

n + 1

is a natural number larger than the supremum, but the supremum is an upper bound of

\mathbb N

Proof workshopRebuild the proof that the natural numbers are not bounded above

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Theorem B Abbott Thm 1.4.3

The rationals are dense

For any real numbers $a < b$ there is a rational $q$ with $a < q < b$ .

In one lineBetween any two real numbers there is a rational number.

Why it is trueChoose a denominator n so fine that steps of size 1/n cannot jump over the gap, then step until you land inside.

ProofAbbott 1.4.3

The idea: Pick n with 1/n smaller than the gap b − a (Archimedean). Then the multiples m/n are spaced closer than the gap, so one of them must land inside (a, b): take the first multiple past a.

Choose

n \in \mathbb N

with

\frac1n < b - a

Archimedean property with

\varepsilon = b - a > 0

Let

m

be the smallest integer with

m > na

. Then

m - 1 \le na < m

The integers above

na

form a non-empty set (Archimedean again) that is bounded below (by

na

), and a non-empty set of integers that is bounded below has a least element. Being least means

m - 1

is not above

na

a < \frac mn

Divide

na < m

n > 0

And

\frac mn \le a + \frac1n < a + (b - a) = b

From

m - 1 \le na

m \le na + 1

, so

\frac mn \le a + \frac1n

, and

\frac1n < b - a

by the choice of

n

q = \frac mn

is rational with

a < q < b

\blacksquare

Both inequalities together.

Worked example

Use the density proof to find a rational number between

1.41421

and

1.41422

Solution.

Find the gap. $b - a = 1.41422 - 1.41421 = 0.00001 = 10^{-5}$ . The proof starts by measuring how wide the gap is, because the grid of fractions must be finer than the gap.
Choose the denominator. We need $\frac1n < 10^{-5}$ , so $n > 100000$ . Take $n = 100001$ . With steps of size $\frac1n$ smaller than the gap, we cannot jump over the interval.
Find the first step past $a$ . $na = 100001 \times 1.41421 = 141422.41421$ , so the smallest integer above it is $m = 141423$ . $m$ is the first multiple of $\frac1n$ that is above $a$ ; the one before it, $141422$ , is at most $na$ .
Form the fraction. $q = \dfrac{141423}{100001} \approx 1.4142158578$ . The proof guarantees $a < q \le a + \frac1n < b$ . Check: $1.41421 < 1.4142158578 < 1.41422$ .

Answer. $q = \frac{141423}{100001}$ is a rational number between $1.41421$ and $1.41422$ (and it is close to $\sqrt 2 \approx 1.41421356$ , as it must be).

Quick checkThe rationals are dense in the reals, yet

\mathbb Q

is not complete. Which statement explains how both can be true?

Worked example Abbott Thm 1.4.5, shortened

Use completeness to prove there is a real number

s

with

s^2 = 2

Solution.

Choose the set. $A = \{ x \in \mathbb R : x > 0,\ x^2 < 2 \}$ . It contains 1, and every element is less than 2 (if $x \ge 2$ then $x^2 \ge 4$ ). So $A$ is non-empty and bounded above, and $s = \sup A$ exists with $s \ge 1$ . Completeness is where the real number $s$ comes from. We have no formula for it yet, so we will find out what $s^2$ must be.
Rule out $s^2 < 2$ (the supremum is too low). Suppose $s^2 < 2$ . For any natural number $n$ , $\left(s + \tfrac1n\right)^2 = s^2 + \tfrac{2s}n + \tfrac1{n^2} \le s^2 + \tfrac{2s + 1}{n}$ , using $\tfrac1{n^2} \le \tfrac1n$ . This is below $2$ as soon as $\tfrac{2s+1}{n} < 2 - s^2$ , that is $n > \dfrac{2s + 1}{2 - s^2}$ , and such an $n$ exists (Archimedean). For that $n$ , $s + \tfrac1n \in A$ and $s + \tfrac1n > s$ , so $s$ is not an upper bound of $A$ . This is a contradiction. The supremum cannot sit inside the region where squares are below 2, because it could then be pushed up a little. The bound on $n$ comes from solving the inequality we want, backwards: scratch work.
Rule out $s^2 > 2$ (the supremum is too high). Suppose $s^2 > 2$ . For any natural number $n$ , $\left(s - \tfrac1n\right)^2 = s^2 - \tfrac{2s}n + \tfrac1{n^2} > s^2 - \tfrac{2s}n$ . This is above 2 as soon as $\tfrac{2s}{n} < s^2 - 2$ , that is $n > \dfrac{2s}{s^2 - 2}$ ; choose such an $n$ (Archimedean). Then $s - \tfrac1n \ge 0$ (as $s \ge 1$ ) and its square is above 2, so $s - \tfrac1n > 0$ . Any $x \in A$ has $x^2 < 2 < \left(s - \tfrac1n\right)^2$ with $x$ and $s - \tfrac1n$ both positive, so $x < s - \tfrac1n$ . So $s - \tfrac1n$ is an upper bound of $A$ that is smaller than $s$ , contradicting that $s$ is the LEAST upper bound. The supremum cannot sit in the region of squares above 2, because it could then be pulled down a little. We drop the positive term $\tfrac1{n^2}$ (that only makes the left side smaller, which is safe for a “greater than” claim).
Conclude. Neither $s^2 < 2$ nor $s^2 > 2$ , so $s^2 = 2$ . Trichotomy: exactly one of $<$ , $=$ , $>$ holds.

Answer. Completeness produces $\sqrt 2$ as the supremum of $A$ . In $\mathbb Q$ the same set has no supremum, which is exactly the hole in the picture.

Quick check

S = \{x \in \mathbb Q : x^2 < 2\}

. In

\mathbb R

, what is

\sup S

, and is it in

S

Quick checkWhich statement is the approximation property of

s = \sup S

How this is used in analysis proofs

The approximation property is a standard move. When a proof involves $s = \sup S$ , it almost always does one of two things:

Uses that $s$ is an upper bound: ” $x \le s$ for all $x \in S$ ”.
Picks $\varepsilon > 0$ and an element $x \in S$ with $x > s - \varepsilon$ .

To prove a claim of the form " $s = \sup S$ " you therefore always do two jobs. Job 1: show $s$ is an upper bound. Job 2: show nothing smaller is, which by the theorem means “for every $\varepsilon > 0$ , find an element of $S$ above $s - \varepsilon$ ”. In job 2 the scratch work is to solve the inequality “element $> s - \varepsilon$ ” for the index of the element, and the write-up then starts with “Let $\varepsilon > 0$ ”.

Worked example

Prove that

\sup\left\{\frac{n}{n+1} : n \in \mathbb N\right\} = 1

Solution.

Guess. The elements are $\frac12, \frac23, \frac34, \dots$ , climbing towards 1. Guess $\sup = 1$ . Scratch work: look at the first few elements.
Job 1: 1 is an upper bound. $\frac{n}{n+1} = 1 - \frac1{n+1} < 1$ for every $n$ . Every element is below 1, which is condition 1 of the definition.
Job 2, scratch work: solve for $n$ . We want an element above $1 - \varepsilon$ : $\frac n{n+1} > 1 - \varepsilon \iff \frac1{n+1} < \varepsilon \iff n + 1 > \frac1\varepsilon$ . We work backwards from the goal to find out how big $n$ must be. Each step can be reversed, so the conditions are equivalent.
Job 2, write-up. Let $\varepsilon > 0$ . By the Archimedean property choose $n \in \mathbb N$ with $n + 1 > \frac1\varepsilon$ . Then $\frac{n}{n+1} = 1 - \frac1{n+1} > 1 - \varepsilon$ . Now the steps run forwards. The tolerance came first, and $n$ was built from it.
Apply the theorem. 1 is an upper bound, and for every $\varepsilon > 0$ some element is above $1 - \varepsilon$ . That is exactly the approximation property, in its “if” direction.

Answer. $\sup = 1$ . For instance $\varepsilon = 0.02$ needs $n + 1 > 50$ , so $n = 50$ gives $\frac{50}{51} \approx 0.9804 > 0.98$ . $\blacksquare$

Your answerFor

S = \{\frac{n}{n+1} : n \in \mathbb N\}

and

\varepsilon = \frac1{50}

, what is the smallest

n

with

\frac n{n+1} > 1 - \varepsilon

Worked example

Prove: if

A

and

B

are non-empty and bounded above, then

\sup(A + B) = \sup A + \sup B

, where

A + B = \{a + b : a \in A,\ b \in B\}

Solution.

Name the suprema. Let $s = \sup A$ and $t = \sup B$ (they exist by completeness). Declare objects first.
$s + t$ is an upper bound. Any element of $A + B$ is $a + b$ with $a \le s$ and $b \le t$ , so $a + b \le s + t$ . Job 1: each supremum is an upper bound.
Set up the approximation. Let $\varepsilon > 0$ . Choose $a \in A$ with $a > s - \frac\varepsilon2$ and $b \in B$ with $b > t - \frac\varepsilon2$ . Job 2, with $\frac\varepsilon2$ each, so the two errors add up to $\varepsilon$ . This is the ” $\varepsilon/2$ trick” you will see constantly. We give each piece half of the budget because we want the total to come out as exactly $\varepsilon$ .
Add. $a + b > \left(s - \frac\varepsilon2\right) + \left(t - \frac\varepsilon2\right) = s + t - \varepsilon$ , and $a + b \in A + B$ . Two strips of width $\frac\varepsilon2$ combine to one of width $\varepsilon$ .
Apply the approximation property backwards. $s + t$ is an upper bound of $A + B$ , and for every $\varepsilon$ there is an element above $s + t - \varepsilon$ . The ( $\Leftarrow$ ) direction of the theorem.

Answer. $\sup(A + B) = s + t$ . $\blacksquare$ The pattern: upper bound by job 1, “nothing smaller works” by job 2 with $\varepsilon$ split between the pieces.

A preview· Preview: monotone sequences

Chapter 1.2 proves that an increasing sequence that is bounded above converges, and the limit is its supremum. The proof is the approximation property, twice. Completeness is exactly what makes that theorem true; over $\mathbb Q$ the sequence $1, 1.4, 1.41, 1.414, \dots$ is increasing and bounded but has no rational limit.

Where it is used

Used inside maths· Inside maths: every big theorem of calculus

The intermediate value theorem (1.3), the extreme value theorem (1.3), the existence of $\int_a^b f$ for continuous $f$ (1.5), the convergence of $\sum \frac1{n^2}$ (1.6) and the existence of solutions to differential equations (7.1) all depend on completeness. Each fails over $\mathbb Q$ .

Used in the real world· Computing: bisection finds roots because of completeness

The bisection method finds a root of $f(x) = x^2 - 2$ by halving $[1, 2]$ again and again, keeping the half where $f$ changes sign. After 30 halvings the interval has width $2^{-30} \approx 9.3 \times 10^{-10}$ . The method is guaranteed to converge to a real number because the left endpoints form an increasing bounded sequence, whose supremum exists by completeness. Root finders in numerical libraries combine fast methods with bisection for exactly this guarantee. For example, MATLAB’s fzero mixes bisection, secant steps and inverse quadratic interpolation.

Traps

Watch out· The supremum need not be in the set

$\sup\{1 - \frac1n\} = 1$ , and 1 is not in the set. A largest element (a maximum) may not exist; a supremum always does for a non-empty set bounded above.

Watch out· 'For every ε, SOME element' (not every element)

The approximation property gives one element near the supremum for each $\varepsilon$ , not all elements. Most elements may be far below.

Watch out· Dense does not mean complete

The rationals are dense (between any two reals there is one) and still have holes. Density is about being everywhere; completeness is about no point missing.

Problems

check

Find $\sup$ and $\inf$ , and say whether each is in the set: (a) $(0, 1]$ ; (b) $\{(-1)^n : n \in \mathbb N\}$ ; (c) $\{\frac1n : n \in \mathbb N\}$ .

Solution

(a) $\sup = 1$ (in), $\inf = 0$ (not in). (b) The set is $\{-1, 1\}$ : $\sup = 1$ , $\inf = -1$ , both in. (c) $\sup = 1$ (in, at $n = 1$ ), $\inf = 0$ (not in), by the Archimedean property.

check

Does $\mathbb Z$ have a supremum in $\mathbb R$ ? Does $\{x \in \mathbb R : x < 5\}$ ?

Solution

$\mathbb Z$ is not bounded above (Archimedean), so no. $\{x : x < 5\}$ has supremum 5 (not in the set).

check

Write the definition of " $s = \sup S$ " with every quantifier visible.

Solution

$(\forall x \in S:\ x \le s) \land (\forall M:\ (\forall x \in S:\ x \le M) \Rightarrow s \le M)$ .

use

Let $S = \{\frac{n}{n + 1} : n \in \mathbb N\}$ . Prove $\sup S = 1$ using the approximation property.

Solution

Upper bound: $\frac{n}{n+1} < 1$ . Approximation: let $\varepsilon > 0$ ; we need $n$ with $\frac n{n+1} > 1 - \varepsilon$ , that is $\frac1{n+1} < \varepsilon$ . By the Archimedean property choose $n$ with $n + 1 > \frac1\varepsilon$ . So $\sup S = 1$ .

use

Prove that between any two real numbers $a < b$ there is an irrational number. (Hint: apply density of $\mathbb Q$ to $\frac{a}{\sqrt 2}$ and $\frac{b}{\sqrt 2}$ .)

Solution

By density there is a rational $q$ with $\frac a{\sqrt2} < q < \frac b{\sqrt2}$ . If $q = 0$ , the interval $\left(0, \frac b{\sqrt2}\right)$ is non-empty, so density gives a rational $q'$ with $0 < q' < \frac b{\sqrt 2}$ ; use $q'$ in place of $q$ . Either way we have a non-zero rational $q$ in the interval. Multiply by $\sqrt 2 > 0$ : $a < q\sqrt 2 < b$ . And $q \sqrt 2$ is irrational: if it equalled a rational $r$ , then $\sqrt 2 = r/q$ would be rational, contradicting 0.2.

use

Let $S$ be non-empty and bounded below. Show $\inf S = -\sup(-S)$ , where $-S = \{-x : x \in S\}$ . Conclude that every non-empty set bounded below has an infimum.

Solution

$m$ is a lower bound of $S$ iff $-m$ is an upper bound of $-S$ (multiplying $x \ge m$ by $-1$ flips it to $-x \le -m$ , and every element of $-S$ has the form $-x$ ). Flipping also reverses “greatest” into “least”: $m$ is a lower bound at least as large as every other lower bound iff $-m$ is an upper bound of $-S$ at most as large as every other upper bound. So $\inf S = -\sup(-S)$ . Since $-S$ is non-empty and bounded above, $\sup(-S)$ exists by completeness, so $\inf S$ exists.

proveAbbott Exercise 1.3.7

Prove: if $a \in S$ and $a$ is an upper bound of $S$ , then $a = \sup S$ .

Solution

$a$ is an upper bound (given). If $M$ is any upper bound, then $a \le M$ because $a \in S$ . So $a$ is the least upper bound.

prove

Prove that the supremum is unique: a set cannot have two different least upper bounds.

Solution

If $s$ and $s'$ are both least upper bounds, then $s \le s'$ (since $s'$ is an upper bound and $s$ is least) and $s' \le s$ (by symmetry). So $s = s'$ .

prove

Let $A \subseteq B$ , both non-empty and bounded above. Prove $\sup A \le \sup B$ .

Solution

$\sup B$ is an upper bound of $B$ , hence of $A$ (every element of $A$ is in $B$ ). Since $\sup A$ is the least upper bound of $A$ , $\sup A \le \sup B$ .

prove

Let $c > 0$ and $cS = \{cx : x \in S\}$ , with $S$ non-empty and bounded above. Prove $\sup(cS) = c \sup S$ .

Solution

Let $s = \sup S$ . Upper bound: $x \le s$ gives $cx \le cs$ . Approximation: let $\varepsilon > 0$ ; choose $x \in S$ with $x > s - \frac\varepsilon c$ . Then $cx > cs - \varepsilon$ . By the approximation property, $\sup(cS) = cs$ .

stretchAbbott Section 1.4

Nested interval property. Let $[a_1, b_1] \supseteq [a_2, b_2] \supseteq \dots$ be closed intervals, each inside the previous. Prove that some real number lies in all of them. (Hint: consider $\sup\{a_n\}$ .) Show the claim fails for the open intervals $(0, \frac1n)$ , and for rational intervals around $\sqrt 2$ if you only allow rational numbers.

Solution

Nesting gives $a_1 \le a_2 \le \dots \le b_m$ for every $m$ : each $a_n \le b_m$ (take $k = \max(n, m)$ : $a_n \le a_k \le b_k \le b_m$ ). So $A = \{a_n\}$ is bounded above by every $b_m$ . Let $x = \sup A$ . Then $a_n \le x$ for all $n$ , and $x \le b_m$ for all $m$ (each $b_m$ is an upper bound and $x$ is least). So $x \in [a_n, b_n]$ for every $n$ . For $(0, \frac1n)$ : a number in all of them would be positive and less than every $\frac1n$ , contradicting the Archimedean property. For rationals: the intervals $[q_n, r_n]$ of rational decimal truncations of $\sqrt 2$ from below and above are nested, but the only real in all of them is $\sqrt 2$ , which is not rational.

Summary

The rationals have holes: a bounded set like $\{q : q^2 < 2\}$ can fail to have a least upper bound in $\mathbb Q$ .
Supremum = least upper bound; infimum = greatest lower bound. They need not belong to the set.
Completeness axiom: every non-empty set of reals that is bounded above has a supremum. This is what “no holes” means.
Approximation property: $s = \sup S$ iff $s$ is an upper bound and for every $\varepsilon > 0$ some $x \in S$ has $x > s - \varepsilon$ . This is the standard move in analysis proofs.
Consequences: $\mathbb N$ is unbounded (Archimedean), the rationals are dense, $\sqrt 2$ exists.
Without completeness, the intermediate value theorem and most of calculus fail.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture: a hole in the rationals

Definitions and theorems

Bounds

Upper bound

Bounded

Supremum

Infimum

The completeness axiom

Completeness axiom

The most-used fact about suprema

Approximation property of the supremum

First consequences

Archimedean property

The reals are Archimedean

The rationals are dense

How this is used in analysis proofs

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere