1.5 The Archimedean Property

We now have the least upper bound axiom (Axiom 1.3.1) and a way to use it, the characterization of the supremum by $\varepsilon$ (Theorem 1.4.1). This section draws the first consequence, one that looks too obvious to need proof: the natural numbers eventually pass every real number. When we first met suprema, we claimed that $\sup \{ 1 - 1/n : n \in \mathbb{Z}_{>0} \} = 1$ and postponed the proof, because it needs exactly this fact. Here we prove the fact from the axiom, pay off that claim, and then meet an ordered field where the fact is false, so that we can see which line of the proof the axiom is holding up.

1.5.1. Where the natural numbers live

So far $\mathbb{R}$ is an ordered field satisfying one extra axiom. The numbers $0, 1, 2, 3, \dots$ are in it, since $2$ is $1 + 1$ , $3$ is $2 + 1$ , and so on. But “and so on” is not a definition. We want the set you get by starting at $0$ and adding $1$ again and again, and nothing else. The first half of that description is easy to state as a property of a set.

Definition 1.5.1 (Inductive set)

A subset $S \subseteq \mathbb{R}$ is inductive if

(N1) $0 \in S$ , and
(N2) for every $x \in S$ , also $x + 1 \in S$ .

In words: an inductive set contains $0$ , and it is closed under the step “add one”. Nothing stops it from containing other numbers as well.

Some examples, checked clause by clause.

$\mathbb{R}$ itself is inductive: it contains $0$ , and $x + 1$ is a real number whenever $x$ is.
$[0, \infty) = \{ x \in \mathbb{R} : x \ge 0 \}$ is inductive: $0 \ge 0$ , and $x \ge 0$ gives $x + 1 \ge 0 + 1 > 0$ .
$\{ 0 \} \cup [1, \infty)$ is inductive. From $0$ we step to $1$ , which is in $[1, \infty)$ , and $[1, \infty)$ is closed under adding $1$ .

A nonexample by minimal change: $[0, 5]$ contains $0$ , so (N1) holds, but $4.5 \in [0, 5]$ and $5.5 \notin [0, 5]$ , so (N2) fails. Chopping the top off $[0, \infty)$ destroys closure under the step.

The inductive sets above are too big: $[0, \infty)$ contains $1.5$ and $4.7$ . What we want is the smallest one. Intersecting all of them throws away everything that some inductive set can do without.

The set of natural numbers is $\mathbb{N} \mathrel{:=} \{ x \in \mathbb{R} : x \in S \text{ for every inductive set } S \subseteq \mathbb{R} \},$ that is, the real numbers that belong to every inductive subset of $\mathbb{R}$ .

Two things are true of $\mathbb{N}$ , and both follow at once from the definition.

$\mathbb{N}$ is inductive. Every inductive set contains $0$ , so $0 \in \mathbb{N}$ . If $x \in \mathbb{N}$ , then $x$ lies in every inductive set $S$ , and each such $S$ then contains $x + 1$ by (N2); so $x + 1 \in \mathbb{N}$ .
$\mathbb{N}$ is contained in every inductive set, since it is their intersection.

The second property is the principle of induction (Logic and Proof, Axiom 4.2.1) in disguise. To prove that a statement $P(n)$ holds for every $n \in \mathbb{N}$ , let $S \mathrel{:=} \{ n \in \mathbb{N} : P(n) \}$ . If $P(0)$ holds and $P(n)$ implies $P(n + 1)$ , then $S$ is inductive, so $\mathbb{N} \subseteq S$ , and $P(n)$ holds for all $n \in \mathbb{N}$ .

Example (Every nonzero natural number is at least 1)

Show that $n \ge 1$ for every $n \in \mathbb{N}$ with $n \ne 0$ , and deduce that for such $n$ , $1/n$ is defined and $0 < 1/n \le 1$ .

Solution. The set $\{ 0 \} \cup [1, \infty)$ is inductive, as checked above. Since $\mathbb{N}$ is contained in every inductive set, $\mathbb{N} \subseteq \{ 0 \} \cup [1, \infty)$ , that is, $n \ge 1$ for every $n \in \mathbb{N}$ with $n \ne 0$ . In particular such an $n$ is positive, so $1/n$ is defined. From $0 < 1 \le n$ Theorem 1.1.2 (f) gives $0 < 1/n \le 1/1 = 1$ .

The proof never mentioned a single natural number by name. It found an inductive set containing the property we wanted, and let the definition of $\mathbb{N}$ do the rest. That is the whole technique.

The nonzero natural numbers are the positive integers, $\mathbb{Z}_{>0} \mathrel{:=} \{ n \in \mathbb{N} : n \ne 0 \} = \{ n \in \mathbb{N} : n \ge 1 \},$ the two descriptions agreeing by Example (Every nonzero natural number is at least 1). This is the set $\{ 1, 2, 3, \dots \}$ that indexed our examples informally before; from here on it is a defined subset of $\mathbb{R}$ , and $1/n$ is defined and positive for every $n \in \mathbb{Z}_{>0}$ .

Remark. Logic and Proof, Chapter 4 takes induction as a basic property of $\mathbb{N}$ (Logic and Proof, Axiom 4.2.1), and Sets, Relations, and Cardinality, Chapter 2 proves well-ordering and the arithmetic below from it. The set defined here is that same $\mathbb{N}$ , now located inside $\mathbb{R}$ ; it is also the copy $0, 1, 1 + 1, 1 + 1 + 1, \dots$ that every ordered field contains (Exercise (C1: Ordered fields contain the counting numbers)), and “ $\mathbb{N}$ is the smallest inductive set” is exactly the induction principle of Logic and Proof, Chapter 4, in the form “every inductive subset of $\mathbb{N}$ is all of $\mathbb{N}$ ”. From now on we use the familiar arithmetic of $\mathbb{N}$ , each item proved by induction in Sets, Relations, and Cardinality, Chapter 2: sums and products of natural numbers are natural numbers; if $n \in \mathbb{N}$ and $n \ge 1$ , then $n - 1 \in \mathbb{N}$ ; no natural number lies strictly between $n$ and $n + 1$ ; and every nonempty subset of $\mathbb{N}$ has a least element (well-ordering). The integers are $\mathbb{Z} \mathrel{:=} \mathbb{N} \cup \{ -n : n \in \mathbb{N} \}$ , and the rationals are $\mathbb{Q} \mathrel{:=} \{ m/n : m \in \mathbb{Z}, \ n \in \mathbb{Z}_{>0} \}$ , with $\mathbb{Z}_{>0}$ the positive integers defined above. We also use, again from Sets, Relations, and Cardinality, Chapter 2, that sums, differences, and products of integers are integers. The integers $n > 0$ are exactly the elements of $\mathbb{Z}_{>0}$ : such an integer is not $-m$ with $m \in \mathbb{N}$ , since $-m \le 0$ , so it is a nonzero natural number; conversely, a nonzero natural number is $> 0$ by Example (Every nonzero natural number is at least 1). So $\mathbb{Z}_{>0} = \{ n \in \mathbb{Z} : n > 0 \}$ .

1.5.2. The natural numbers are not bounded

Is $\mathbb{N}$ bounded above in $\mathbb{R}$ ? Everyone’s picture of the number line says no: the marks $1, 2, 3, \dots$ march off to the right forever. But a picture is not a proof, and here the picture hides something. Nothing in the ordered-field axioms (Definition 1.1.1) forbids a number larger than every natural number. At the end of this section we build an ordered field that contains one. So if $\mathbb{R}$ has no such number, the reason must be the one axiom that $\mathbb{R}$ has and that field lacks.

Theorem 1.5.1 (Archimedean Property)

The set $\mathbb{N}$ is not bounded above in $\mathbb{R}$ ; in other words, every real number $x$ is exceeded by some $n \in \mathbb{N}$ .

Idea. Suppose $\mathbb{N}$ had an upper bound. Then the axiom hands us the least one, $s = \sup \mathbb{N}$ . Every natural number $n$ has a successor $n + 1$ that is still a natural number, and so still at most $s$ . Moving back one step, $n \le s - 1$ for every $n$ : the smaller number $s - 1$ is an upper bound too. A least upper bound with a smaller upper bound below it is absurd.

Proof. Suppose, for contradiction, that $\mathbb{N}$ is bounded above. The set $\mathbb{N}$ is nonempty, since $0 \in \mathbb{N}$ . By Axiom 1.3.1, $\mathbb{N}$ has a supremum $s \mathrel{:=} \sup \mathbb{N} \in \mathbb{R}$ .

Let $n \in \mathbb{N}$ . Since $\mathbb{N}$ is inductive, $n + 1 \in \mathbb{N}$ , and since $s$ is an upper bound of $\mathbb{N}$ , $n + 1 \le s$ , that is, $n \le s - 1$ . As $n$ was arbitrary, $s - 1$ is an upper bound of $\mathbb{N}$ . Property (S2) of the supremum (Definition 1.2.4) now gives $s \le s - 1$ , that is, $1 \le 0$ , which contradicts $0 < 1$ .

Therefore $\mathbb{N}$ is not bounded above. Unwinding the definition (Definition 1.2.2), no $x \in \mathbb{R}$ is an upper bound of $\mathbb{N}$ : for every $x \in \mathbb{R}$ it is false that $n \le x$ for all $n \in \mathbb{N}$ . So for every $x$ some $n \in \mathbb{N}$ has $n \not\le x$ , that is, $n > x$ by trichotomy. This proves the theorem.

Each hypothesis of the axiom was used and named: “nonempty” through $0 \in \mathbb{N}$ , “bounded above” through the assumption for contradiction. The inductive property of $\mathbb{N}$ supplied the jump $n \mapsto n + 1$ .

Remark. The contradiction step is $\mathrm{\neg I}$ (Logic and Proof, Definition 2.2.1), not $\mathrm{RAA}$ (Logic and Proof, Definition 2.5.1), the classical rule of proof by contradiction: we assumed “ $\mathbb{N}$ is bounded above”, reached a contradiction, and concluded its negation. Inside that box every step is direct. The proof shows that $s - 1$ is an upper bound; it does not argue “ $s - 1$ is not an upper bound, so some $n$ exceeds $s - 1$ ”, a step that would itself need the classical law described next. The proof’s one classical step comes after the $\mathrm{\neg I}$ , in its last paragraph. Passing from “not every $n$ satisfies $n \le x$ ” to “some $n$ satisfies $n > x$ ” is the quantifier law “not all” gives “some not” of Logic and Proof, Chapter 6, and that law is derived there with $\mathrm{RAA}$ .

The form we will use most often puts a small number, not a large one, in the role of $x$ .

Corollary 1.5.2

For every $\varepsilon > 0$ there is $n \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ . In symbols, $(\forall \varepsilon > 0)\ (\exists n \in \mathbb{Z}_{>0}) \quad \frac{1}{n} < \varepsilon .$ Moreover, every $m \in \mathbb{Z}_{>0}$ with $m \ge n$ then also satisfies $1/m < \varepsilon$ .

Proof. Let $\varepsilon > 0$ . Then $1/\varepsilon$ is defined and positive. By Theorem 1.5.1 applied to $x = 1/\varepsilon$ , there is $n \in \mathbb{N}$ with $n > 1/\varepsilon > 0$ ; so $n \in \mathbb{Z}_{>0}$ . Taking reciprocals reverses a strict inequality between positive numbers (Theorem 1.1.2 (f)), so $1/n < \varepsilon$ . If $m \ge n$ , then $1/m \le 1/n < \varepsilon$ by the same rule.

Read the quantifiers in order. The $\varepsilon$ is given first and the $n$ is found afterwards, so $n$ depends on $\varepsilon$ : the proof chose $n > 1/\varepsilon$ , and a smaller $\varepsilon$ forces a larger $n$ . Swapping the quantifiers gives a false statement. “There is $n \in \mathbb{Z}_{>0}$ such that $1/n < \varepsilon$ for every $\varepsilon > 0$ ” would make $1/n$ smaller than every positive number. Since $1/n > 0$ (Example (Every nonzero natural number is at least 1)), we could take $\varepsilon = 1/n$ itself and get $1/n < 1/n$ , which is absurd.

The “moreover” clause says that once one $n$ works, every later one works too. Chapter 2 turns this “from some point on” into the definition of a limit.

Quick check. Find the least $n \in \mathbb{Z}_{>0}$ with $1/n < 0.003$ . Then do the same for $\varepsilon = 0.0003$ . What does the comparison say about the dependence of $n$ on $\varepsilon$ ?

Solution. For positive $n$ , $1/n < 0.003$ is equivalent to $n > 1/0.003 = 333.\overline{3}$ . The least positive integer with this property is $n = 334$ ; indeed $1/333 = 0.003003\ldots$ is too big. For $\varepsilon = 0.0003$ the condition is $n > 3333.\overline{3}$ , so the least $n$ is $3334$ . Dividing $\varepsilon$ by $10$ multiplied the least $n$ by about $10$ . No single $n$ serves every $\varepsilon$ , which is why the quantifiers read “for every $\varepsilon$ there is $n$ ” and not the other way round.

1.5.3. Paying an old debt

In Example (A supremum we cannot yet prove) we showed that $1$ is an upper bound of $A = \{ 1 - 1/n : n \in \mathbb{Z}_{>0} \}$ and that $A$ has no maximum. We stopped short of $\sup A = 1$ , because (S2) needed an $n$ with $1/n$ below a given positive number. That is exactly what Corollary 1.5.2 supplies, and the $\varepsilon$ -characterization tells us what remains to be shown.

Example (The supremum is 1)

Let $A \mathrel{:=} \{ 1 - 1/n : n \in \mathbb{Z}_{>0} \}$ . Prove that $\sup A = 1$ .

Solution. The set $A$ is nonempty, since $0 = 1 - 1/1 \in A$ .

Upper bound. For every $n \in \mathbb{Z}_{>0}$ we have $1/n > 0$ (Example (Every nonzero natural number is at least 1)), so $1 - 1/n < 1$ . Hence $1$ is an upper bound of $A$ .

An element in every band below $1$ . Let $\varepsilon > 0$ . By Corollary 1.5.2 there is $n \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ ; this $n$ depends on $\varepsilon$ . Then $a \mathrel{:=} 1 - 1/n \in A$ and $a > 1 - \varepsilon$ .

Since $1$ is an upper bound of $A$ and every band $(1 - \varepsilon, 1]$ contains an element of $A$ , Theorem 1.4.1 gives $\sup A = 1$ .

For a concrete instance, $\varepsilon = 0.01$ needs $n > 100$ , and $n = 101$ gives the element $1 - 1/101 = 100/101 > 0.99$ . Together with Example (A supremum we cannot yet prove), $A$ is a set whose supremum $1$ is not attained.

The pattern of this example, “upper bound, then an element in every band below it”, is the one every supremum computation in this book follows. The only new input here was Corollary 1.5.2, which turns “ $1/n$ is small” into a precise choice of $n$ .

1.5.4. An ordered field without the Archimedean property

We claimed that the Archimedean property does not follow from the ordered-field axioms alone. Now we back that up with a concrete field containing an element larger than every natural number. The field is made of fractions of polynomials, and the element is the variable $x$ itself.

A rational function is a quotient $p/q$ of real polynomials $p$ and $q$ with $q$ not the zero polynomial. Two quotients $p/q$ and $p'/q'$ are the same element when $p q' = p' q$ , exactly as for fractions of integers. With the usual addition and multiplication of fractions, the rational functions form a field, written $\mathbb{R}(x)$ . This is the same construction that builds $\mathbb{Q}$ out of $\mathbb{Z}$ , applied to polynomials; it is algebra, and we take it as known without proof here. The real numbers sit inside $\mathbb{R}(x)$ as the constant functions.

The leading coefficient of a nonzero polynomial is the coefficient of its highest power of $x$ . For instance, the leading coefficient of $3 - 2x^2$ is $-2$ .

Call a nonzero $p/q \in \mathbb{R}(x)$ positive if the leading coefficients of $p$ and $q$ are both positive or both negative, and write $f < g$ when $g - f$ is positive.

Here is the picture behind this definition. For large real $t$ , the value $p(t)/q(t)$ has the sign of the product of the two leading coefficients, because the top powers dominate. So “ $f > 0$ ” means “ $f(t) > 0$ for all sufficiently large $t$ ”, and $f < g$ means that the graph of $g$ eventually lies above the graph of $f$ . This is only a picture: the definition uses leading coefficients and nothing else.

Positivity does not depend on how the fraction is written. Suppose $p/q = p'/q'$ , so that $p q' = p' q$ , and let $\alpha, \beta, \alpha', \beta'$ be the leading coefficients of $p, q, p', q'$ . The leading coefficient of a product of polynomials is the product of their leading coefficients, so $\alpha \beta' = \alpha' \beta$ . Multiplying both sides by $\beta \beta'$ gives $\alpha\beta \cdot \beta'^2 = \alpha'\beta' \cdot \beta^2$ , and $\beta^2, \beta'^2 > 0$ . Hence $\alpha\beta$ and $\alpha'\beta'$ have the same sign: $p/q$ is positive exactly when $p'/q'$ is.

With this order $\mathbb{R}(x)$ is an ordered field. The key facts are that sums and products of positive elements are positive, and that for each nonzero $f$ exactly one of $f$ and $-f$ is positive. Checking these is routine, and Exercise (C2: The order on the rational functions) walks through them. On the constants, the new order is the old one: the constant $c$ is positive exactly when $c > 0$ . The example below uses that $\mathbb{R}(x)$ is an ordered field, and with it the rules of Theorem 1.1.2, which hold in every ordered field; so it rests on Exercise (C2: The order on the rational functions), where that is proved.

The natural numbers of $\mathbb{R}(x)$ , the smallest inductive subset in the sense of Definition 1.5.1, are the constants $0, 1, 2, 3, \dots$ . Indeed, the constant functions $n$ with $n \in \mathbb{N}$ form an inductive subset of $\mathbb{R}(x)$ : it contains the constant $0$ , and the constant $n$ plus $1$ is the constant $n + 1$ . So every natural number of $\mathbb{R}(x)$ is such a constant. Conversely, let $I$ be an inductive subset of $\mathbb{R}(x)$ . The set of $n \in \mathbb{N}$ whose constant lies in $I$ contains $0$ and passes from $n$ to $n + 1$ , so it is an inductive subset of $\mathbb{R}$ and contains all of $\mathbb{N}$ . So every constant $n$ lies in every inductive subset of $\mathbb{R}(x)$ .

Example (A non-Archimedean field)

In $\mathbb{R}(x)$ with the order just described, show that $n < x$ for every $n \in \mathbb{N}$ . Deduce that $\mathbb{N}$ is bounded above in $\mathbb{R}(x)$ , and that Corollary 1.5.2 fails in $\mathbb{R}(x)$ .

Solution. Let $n \in \mathbb{N}$ . Then $x - n = (x - n)/1$ . The numerator $x - n$ has leading coefficient $1$ and the denominator $1$ has leading coefficient $1$ . They have the same sign, so $x - n$ is positive, that is, $n < x$ .

Hence $x$ is an upper bound of $\mathbb{N}$ in $\mathbb{R}(x)$ , and $\mathbb{N}$ is bounded above there. So the conclusion of Theorem 1.5.1 is false in $\mathbb{R}(x)$ .

Now take $\varepsilon \mathrel{:=} 1/x$ . It is positive: numerator $1$ and denominator $x$ both have leading coefficient $1$ . For each $n \in \mathbb{Z}_{>0}$ we have $0 < n < x$ , so taking reciprocals gives $1/x < 1/n$ . No positive integer $n$ satisfies $1/n < \varepsilon$ , and Corollary 1.5.2 fails.

The element $1/x$ is positive yet smaller than every $1/n$ : an “infinitely small” number. The real line has none, and that is exactly what Corollary 1.5.2 says.

1.5.5. The line of the proof that fails

Every step in the proof of Theorem 1.5.1, except one, is valid in any ordered field. So let us run the proof in $\mathbb{R}(x)$ and watch where it breaks.

“Suppose $\mathbb{N}$ is bounded above.” In $\mathbb{R}(x)$ this is true, with upper bound $x$ .
“ $\mathbb{N}$ is nonempty.” True.
“By Axiom 1.3.1, $\mathbb{N}$ has a supremum $s$ .” This is the line that fails. In $\mathbb{R}(x)$ , $\mathbb{N}$ has no least upper bound at all. Indeed, let $M$ be any upper bound of $\mathbb{N}$ in $\mathbb{R}(x)$ . For each $n \in \mathbb{N}$ , also $n + 1 \in \mathbb{N}$ , so $n + 1 \le M$ , that is, $n \le M - 1$ . Hence $M - 1$ is also an upper bound, and it is strictly smaller than $M$ . No upper bound is the least one.
The remaining lines, “ $n + 1 \le s$ for every $n \in \mathbb{N}$ , so $s - 1$ is an upper bound, and (S2) gives $s \le s - 1$ ”, use only the ordered-field axioms and the fact that $\mathbb{N}$ is inductive. They would go through in $\mathbb{R}(x)$ if there were an $s$ to apply them to.

The argument that shows $\mathbb{N}$ has no supremum in $\mathbb{R}(x)$ is the middle paragraph of the proof of Theorem 1.5.1, with $M$ in place of $s$ . That proof showed that a supremum of $\mathbb{N}$ cannot exist in any ordered field; the axiom then says that, in $\mathbb{R}$ , a bounded $\mathbb{N}$ would have to have one. In $\mathbb{R}(x)$ there is no axiom to force it, so no contradiction arises. Two conclusions follow:

$\mathbb{R}(x)$ is an ordered field in which Axiom 1.3.1 fails, with witness the nonempty, bounded-above set $\mathbb{N}$ .
In any ordered field, the least upper bound axiom implies the Archimedean property. That is precisely what our proof showed.

Warning. The Archimedean property is not “obvious”, and it is not a consequence of the ordered-field axioms. It is exactly what $\mathbb{R}(x)$ lacks, where $x$ exceeds every natural number. In $\mathbb{R}$ it holds only because of the least upper bound axiom. A proof that says “choose an integer larger than $x$ ” is using Theorem 1.5.1, and should cite it.

Remark. The converse fails: an ordered field can be Archimedean without satisfying the axiom. The field $\mathbb{Q}$ is one (Exercise (C3: Archimedean without the axiom)), and it fails the axiom by Theorem 1.2.2. So the Archimedean property is strictly weaker than the axiom. Chapter 11 shows which properties, added to the Archimedean property, bring back the full axiom.

1.5.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Write the Archimedean property “for every $x \in \mathbb{R}$ there is $n \in \mathbb{N}$ with $n > x$ ” in symbols, and write its negation in symbols.
(b) Which of the following subsets of $\mathbb{R}$ are inductive: $[\tfrac12, \infty)$ , $[0, 10]$ , $\mathbb{N} \cup \{ \tfrac12 \}$ , $\mathbb{Z}$ ? Name the failing clause for each one that is not.
(c) True or false, with a reason: in Corollary 1.5.2, one $n$ can be chosen that works for every $\varepsilon > 0$ .
(d) In the proof of Theorem 1.5.1, which line uses the least upper bound axiom, and which line uses that $\mathbb{N}$ is inductive?

Solution.

(a) The property is $(\forall x \in \mathbb{R})(\exists n \in \mathbb{N})\ n > x$ . Its negation is $(\exists x \in \mathbb{R})(\forall n \in \mathbb{N})\ n \le x$ : some real number is an upper bound of $\mathbb{N}$ .
(b) $[\tfrac12, \infty)$ is not: $0 \notin [\tfrac12, \infty)$ , so (N1) fails, although $x \ge \tfrac12$ gives $x + 1 \ge \tfrac32 \ge \tfrac12$ , so (N2) holds. $[0, 10]$ is not: it contains $0$ , but $10 \in [0, 10]$ and $11 \notin [0, 10]$ , so (N2) fails. $\mathbb{N} \cup \{ \tfrac12 \}$ is not: $\tfrac12$ is in it but $\tfrac32$ is not, since $\tfrac32$ lies strictly between the natural numbers $1$ and $2$ ; so (N2) fails. $\mathbb{Z}$ is inductive: $0 \in \mathbb{Z}$ , and $k + 1 \in \mathbb{Z}$ for every integer $k$ .
(c) False. Such an $n$ would satisfy $1/n < \varepsilon$ for every $\varepsilon > 0$ . But $1/n > 0$ by Example (Every nonzero natural number is at least 1), so $\varepsilon = 1/n$ is allowed, and it gives $1/n < 1/n$ , which is absurd. The $n$ must depend on $\varepsilon$ .
(d) The axiom is used in “ $\mathbb{N}$ has a supremum $s$ ”. That $\mathbb{N}$ is inductive is used in “ $n + 1 \in \mathbb{N}$ ”.

B. Practice

Exercise (B1: An infimum)

Prove that $\inf \{ 1/n : n \in \mathbb{Z}_{>0} \} = 0$ , and that the set has no minimum.

Solution. Let $B \mathrel{:=} \{ 1/n : n \in \mathbb{Z}_{>0} \}$ ; it is nonempty, since $1 \in B$ . By Example (Every nonzero natural number is at least 1), $1/n > 0$ for every $n$ , so $0$ is a lower bound of $B$ .

Let $L$ be any lower bound of $B$ ; we show $L \le 0$ . Suppose instead $L > 0$ . By Corollary 1.5.2 with $\varepsilon = L$ , there is $n \in \mathbb{Z}_{>0}$ with $1/n < L$ . This contradicts $L$ being a lower bound of $B$ . Hence $L \le 0$ . So $0$ is a lower bound that is greater than or equal to every lower bound, that is, $\inf B = 0$ (Definition 1.2.5).

Since $0 \notin B$ (every element is positive), the infimum is not attained, and $B$ has no minimum.

Exercise (B2: Scaled Archimedes)

Let $a > 0$ and $y \in \mathbb{R}$ . Prove that there is $n \in \mathbb{N}$ with $n a > y$ . What does this say when $a$ is the length of a measuring stick?

Solution. Since $a > 0$ , the number $y/a$ is defined. By Theorem 1.5.1 there is $n \in \mathbb{N}$ with $n > y/a$ ; the $n$ depends on $y$ and $a$ . Multiplying by $a > 0$ preserves the strict inequality (Theorem 1.1.2 (c)), so $n a > y$ .

In words: laying a stick of length $a$ , however short, end to end enough times carries you past any given point $y$ , however far away. This is the form in which Archimedes used the property.

Exercise (B3: Smaller than every 1/n)

Let $x \in \mathbb{R}$ with $0 \le x < 1/n$ for every $n \in \mathbb{Z}_{>0}$ . Prove that $x = 0$ . Then deduce: if $a, b \in \mathbb{R}$ satisfy $\left| a - b \right| < 1/n$ for every $n \in \mathbb{Z}_{>0}$ , then $a = b$ .

Solution. Suppose $x \ne 0$ . Since $x \ge 0$ , we get $x > 0$ . By Corollary 1.5.2 with $\varepsilon = x$ , there is $n \in \mathbb{Z}_{>0}$ with $1/n < x$ , contradicting the hypothesis $x < 1/n$ . Hence $x = 0$ .

For the second statement, put $x \mathrel{:=} \left| a - b \right|$ . Then $0 \le x < 1/n$ for every $n$ , so $x = 0$ by the first part, that is, $a = b$ .

This is how equality is proved in analysis over and over: show that the distance is nonnegative and smaller than every $1/n$ .

Exercise (B4: Putting a proof in order)

Here are nine lines. Seven of them, in a suitable order, prove that $\sup A = 1$ for $A \mathrel{:=} \{ \frac{n}{n + 1} : n \in \mathbb{N} \}$ . Give an admissible order. Then say why each of the other two lines cannot be used.

(i) Let $\varepsilon > 0$ .
(ii) Hence $a \mathrel{:=} \frac{n}{n + 1}$ is an element of $A$ with $a > 1 - \varepsilon$ .
(iii) For every $n \in \mathbb{N}$ , $n < n + 1$ and $n + 1 > 0$ , so $\frac{n}{n + 1} < 1$ . Hence $1$ is an upper bound of $A$ .
(iv) By Corollary 1.5.2 there is $n \in \mathbb{Z}_{>0}$ , depending on $\varepsilon$ , with $\frac1n < \varepsilon$ .
(v) Choose $n \in \mathbb{Z}_{>0}$ such that $\frac1n < \varepsilon$ for every $\varepsilon > 0$ .
(vi) Since $\varepsilon > 0$ was arbitrary, every band $(1 - \varepsilon, 1]$ contains an element of $A$ .
(vii) Then $\frac{n}{n + 1} = 1 - \frac1{n + 1}$ , and $\frac1{n + 1} < \frac1n < \varepsilon$ .
(viii) By Theorem 1.4.1, $\sup A = 1$ .
(ix) Fix $n \in \mathbb{Z}_{>0}$ and let $\varepsilon \mathrel{:=} \frac1n$ ; then $\frac{n}{n + 1} = 1 - \frac1{n + 1} > 1 - \varepsilon$ .

Solution. An admissible order is (iii), (i), (iv), (vii), (ii), (vi), (viii). The line (iii) may stand anywhere before (viii), since it uses nothing but the definition of $A$ . The other lines admit only this order. Inside the block that starts with (i), line (iv) needs the $\varepsilon$ of (i), line (vii) needs the $n$ of (iv), line (ii) needs (vii), and (vi) records that $\varepsilon$ was arbitrary. Line (viii) needs both (iii) and (vi), the two hypotheses of Theorem 1.4.1.

Line (v) has the quantifiers in the wrong order. It asks for one $n$ that works for every $\varepsilon$ , and there is none: $\varepsilon = \frac1n$ itself would give $\frac1n < \frac1n$ . Corollary 1.5.2 gives an $n$ for each $\varepsilon$ .

Line (ix) is true, but its $\varepsilon$ is of the wrong kind: it is chosen to fit $n$ , instead of being given first. It shows only that the bands of the special widths $\frac1n$ meet $A$ , while Theorem 1.4.1 needs every band, of every width $\varepsilon > 0$ . Passing from the special widths to all widths is exactly the work of lines (iv) and (vii), which (ix) skips.

C. Going deeper

Exercise (C1: Exit check: the Archimedean property, and a circular proof)

(a) Without looking back, prove the Archimedean property from the least upper bound axiom. Mark the line that uses the axiom, and explain why that line fails in $\mathbb{R}(x)$ .
(b) A student offers the following proof. “Let $x \in \mathbb{R}$ . Let $n \mathrel{:=} \left\lceil x \right\rceil + 1$ , where $\left\lceil x \right\rceil$ is the least integer that is greater than or equal to $x$ . Then $n > x$ .” Find the gap. Show that in $\mathbb{R}(x)$ the element $x$ has no “least integer greater than or equal to it”.

Solution.

(a) Suppose $\mathbb{N}$ is bounded above in $\mathbb{R}$ . Since $0 \in \mathbb{N}$ , the set is nonempty, so by Axiom 1.3.1 it has a supremum $s$ (this line uses the axiom). For every $n \in \mathbb{N}$ , also $n + 1 \in \mathbb{N}$ , since $\mathbb{N}$ is inductive, so $n + 1 \le s$ by (S1), that is, $n \le s - 1$ . Hence $s - 1$ is an upper bound of $\mathbb{N}$ , and (S2) gives $s \le s - 1$ , which is false. So $\mathbb{N}$ is not bounded above, which means that every $x \in \mathbb{R}$ is exceeded by some $n \in \mathbb{N}$ .
In $\mathbb{R}(x)$ the set $\mathbb{N}$ is nonempty and bounded above by $x$ (Example (A non-Archimedean field)), but it has no supremum. Any upper bound $M$ gives a smaller one, $M - 1$ , because $n + 1 \le M$ for every $n \in \mathbb{N}$ forces $n \le M - 1$ . So the marked line has nothing to produce, and there the proof stops.
(b) The gap is the existence of $\left\lceil x \right\rceil$ . The set $\{ k \in \mathbb{Z} : k \ge x \}$ has a least element only if it is nonempty, and it is nonempty exactly when some integer is at least $x$ . That is (a form of) the Archimedean property, the statement being proved. The proof is circular.

In $\mathbb{R}(x)$ , take the element $x$ and suppose $k \in \mathbb{Z}$ satisfies $k \ge x$ . If $k \le 0$ , then $k \le 0 < 1 < x$ . If $k \ge 1$ , then $k \in \mathbb{N}$ and $k < x$ by Example (A non-Archimedean field). Either way $k < x$ , a contradiction. So no integer is greater than or equal to $x$ , and $\left\lceil x \right\rceil$ does not exist.

Marking scheme. (10 points) - 1: (a) supposes, for a contradiction, that $\mathbb{N}$ is bounded above, and notes $0 \in \mathbb{N}$ . - 2: (a) obtains $s = \sup \mathbb{N}$ from Axiom 1.3.1, with both hypotheses checked, and marks this line. - 2: (a) shows that $s - 1$ is an upper bound of $\mathbb{N}$ : $n + 1 \in \mathbb{N}$ because $\mathbb{N}$ is inductive, so $n + 1 \le s$ by (S1), that is, $n \le s - 1$ , for every $n \in \mathbb{N}$ . - 1: (a) applies the “least” property (S2) to the upper bound $s - 1$ , reaches $s \le s - 1$ , a contradiction, and concludes. - 1: (a) explains why the marked line fails in $\mathbb{R}(x)$ : every upper bound $M$ of $\mathbb{N}$ there has the smaller upper bound $M - 1$ . - 2: (b) names the existence of $\left\lceil x \right\rceil$ as the gap, and says it already needs an integer at least $x$ , which is what is being proved. - 1: (b) shows that no integer is at least $x$ in $\mathbb{R}(x)$ . Fatal errors (0 for the step): taking $s$ to be a natural number, or the maximum of $\mathbb{N}$ ; omitting “for every $n$ ” (one $n$ with $n \le s - 1$ does not make $s - 1$ an upper bound); using $\left\lceil x \right\rceil$ , $\left\lfloor x \right\rfloor$ , or the Archimedean property inside (a). A proof of (a) that argues “by (S2), or Theorem 1.4.1 with $\varepsilon = 1$ , $s - 1$ is not an upper bound, so some $n > s - 1$ , and then $n + 1 > s$ ” is also correct and earns the same 3 points for those steps; it uses one more classical step, inside the box (the remark after Theorem 1.5.1). A proof of (a) that applies the axiom to a bounded set of the form $\{ n \in \mathbb{N} : n \le x \}$ instead earns full marks for (a) if it reaches a contradiction from the supremum in the same way.

Exercise (C2: The order on the rational functions)

Let $P \subseteq \mathbb{R}(x)$ be the set of positive elements defined in this section, and let $f < g$ mean $g - f \in P$ .

(a) Show that every nonzero $f \in \mathbb{R}(x)$ can be written as $p/q$ with the leading coefficient of $q$ positive, and that then $f \in P$ if and only if the leading coefficient of $p$ is positive.
(b) Show that for every nonzero $f$ , exactly one of $f \in P$ and $-f \in P$ holds.
(c) Show that if $f, g \in P$ , then $f g \in P$ and $f + g \in P$ .
(d) Deduce the order axioms of Definition 1.1.1 for $<$ : trichotomy, transitivity, $f < g \Rightarrow f + h < g + h$ , and $f, g > 0 \Rightarrow f g > 0$ .

Solution (Hint 1). Choose good representatives first. Every fraction can be rewritten so that its denominator has positive leading coefficient, and after that only the numerator decides positivity.

Solution (Hint 2). For the sum in (c), with both denominators normalized, write $f + g = (p_1 q_2 + p_2 q_1)/(q_1 q_2)$ and split into two cases: the two terms of the numerator have different degrees, or the same degree.

Solution. Write $\operatorname{lc}(p)$ for the leading coefficient of a nonzero polynomial $p$ . Recall that $\operatorname{lc}(pq) = \operatorname{lc}(p)\operatorname{lc}(q)$ , since the top powers multiply.

(a) Let $f = p/q$ . If $\operatorname{lc}(q) < 0$ , then $f = (-p)/(-q)$ and $\operatorname{lc}(-q) = -\operatorname{lc}(q) > 0$ . So we may assume $\operatorname{lc}(q) > 0$ . Then “ $\operatorname{lc}(p)$ and $\operatorname{lc}(q)$ have the same sign” means exactly $\operatorname{lc}(p) > 0$ . By the well-definedness shown in the section, this does not depend on the chosen representation.
(b) Write $f = p/q$ with $\operatorname{lc}(q) > 0$ , as in (a). Then $-f = (-p)/q$ and $\operatorname{lc}(-p) = -\operatorname{lc}(p)$ . Since $p \ne 0$ , $\operatorname{lc}(p)$ is a nonzero real number, so by trichotomy in $\mathbb{R}$ exactly one of $\operatorname{lc}(p) > 0$ and $-\operatorname{lc}(p) > 0$ holds. By (a), exactly one of $f \in P$ and $-f \in P$ holds.
(c) Write $f = p_1/q_1$ and $g = p_2/q_2$ with all four leading coefficients positive, using (a). The product is $f g = (p_1 p_2)/(q_1 q_2)$ with $\operatorname{lc}(p_1 p_2) = \operatorname{lc}(p_1)\operatorname{lc}(p_2) > 0$ and $\operatorname{lc}(q_1 q_2) > 0$ , so $f g \in P$ . The sum is $f + g = \frac{p_1 q_2 + p_2 q_1}{q_1 q_2}.$ Both $p_1 q_2$ and $p_2 q_1$ have positive leading coefficient. If their degrees differ, the leading coefficient of the sum is that of the term of higher degree, which is positive. If their degrees agree, it is the sum of the two leading coefficients, which is positive. In both cases the numerator is nonzero with positive leading coefficient, and $\operatorname{lc}(q_1 q_2) > 0$ , so $f + g \in P$ .
(d) Trichotomy. Given $f, g$ , either $g - f = 0$ , or $g - f \ne 0$ and by (b) exactly one of $g - f \in P$ and $f - g = -(g - f) \in P$ holds. So exactly one of $f = g$ , $f < g$ , $g < f$ holds.

Transitivity. If $f < g$ and $g < h$ , then $g - f \in P$ and $h - g \in P$ , so $h - f = (h - g) + (g - f) \in P$ by (c); that is, $f < h$ .

Addition. If $f < g$ , then $(g + h) - (f + h) = g - f \in P$ , so $f + h < g + h$ .

Products. If $f > 0$ and $g > 0$ , then $f = f - 0 \in P$ and $g \in P$ , so $f g \in P$ by (c); that is, $f g > 0$ .

Exercise (C3: Archimedean without the axiom)

(a) Prove, without using Axiom 1.3.1, that for every $r \in \mathbb{Q}$ there is $n \in \mathbb{N}$ with $n > r$ .
(b) Deduce that the Archimedean property does not imply the least upper bound axiom in an ordered field.

Solution.

(a) Write $r = m/k$ with $m \in \mathbb{Z}$ and $k \in \mathbb{Z}_{>0}$ . If $m \le 0$ , then $r \le 0 < 1$ , and $n = 1$ works. If $m \ge 1$ , then $m \in \mathbb{N}$ . Since $k \ge 1$ (Example (Every nonzero natural number is at least 1)) and $m > 0$ , we get $r = m/k \le m < m + 1$ , and $n \mathrel{:=} m + 1 \in \mathbb{N}$ works. No supremum was used: only the arithmetic of integers and the ordered-field rules.
(b) By (a), $\mathbb{Q}$ is an ordered field in which $\mathbb{N}$ is not bounded above, so $\mathbb{Q}$ has the Archimedean property. By Theorem 1.2.2, the nonempty set $\{ x \in \mathbb{Q} : x > 0, \ x^2 < 2 \}$ , which is bounded above by $2$ , has no supremum in $\mathbb{Q}$ . So $\mathbb{Q}$ is Archimedean and fails the least upper bound axiom, and the Archimedean property cannot imply the axiom.