1.6 Density of the Rationals and the Existence of Roots

When we first met suprema, Theorem 1.2.2 showed that the set of positive rationals whose square is less than $2$ has no supremum in $\mathbb{Q}$ . In $\mathbb{R}$ the axiom gives that set a supremum. This section finds out what the supremum is: a positive number whose square is exactly $2$ . The same template produces every root $a^{1/n}$ . With roots in hand, and with the Archimedean property of the previous section, we then answer a question about arrangement: the rationals and the irrationals are both spread through every interval of the line, however short.

1.6.1. Constructing a point as a supremum

Logic and Proof, Chapter 2 showed that no rational number squares to $2$ (Logic and Proof, Theorem 2.2.1). Nothing so far says that any real number does. The ordered-field axioms cannot say it, since $\mathbb{Q}$ satisfies them all. So if a square root of $2$ exists in $\mathbb{R}$ , the least upper bound axiom must produce it.

Theorem 1.6.1 (The Square Root of Two Exists)

There is exactly one real number $s > 0$ with $s^2 = 2$ .

Try it first (ten minutes): the axiom is the only statement we have that produces a real number. To which set would you apply it, and what would you then have to show?

Idea. The obvious attempts do not get started. There is no formula for $\sqrt 2$ in terms of rationals, and the decimals $1, 1.4, 1.41, \dots$ of the chapter’s introduction would need a limit, which we do not have yet. The only statement that produces a real number is Axiom 1.3.1, so $\sqrt 2$ will have to be a supremum, and Theorem 1.2.2 suggests which one. Collect the positive reals whose square is below $2$ into a set $S$ . The candidate is $s = \sup S$ . The plan has three steps: ① check that $S$ is nonempty and bounded above, so the axiom supplies $s$ ; ② rule out $s^2 < 2$ ; ③ rule out $s^2 > 2$ . Trichotomy then leaves $s^2 = 2$ .

Each case is ruled out by nudging $s$ . If $s^2 < 2$ , there is still room below $2$ , so a slightly larger number $s + h$ is still in $S$ . That is impossible for an upper bound. If $s^2 > 2$ , a slightly smaller number $s - h$ still has square above $2$ , and is therefore still an upper bound. That is impossible for the least upper bound.

The nudges are the ones found in Theorem 1.2.2, where they were derived backwards from the goal. To recall the first: we want $(s + h)^2 = s^2 + 2sh + h^2 < 2$ . If $h \le 1$ , then $h^2 \le h$ , so $(s + h)^2 \le s^2 + (2s + 1)h$ . Letting $(2s + 1)h$ use half of the room $2 - s^2$ gives $h = (2 - s^2)/(4s + 2)$ , and we must then check $h \le 1$ . For the second nudge, $(s - h)^2 > s^2 - 2sh$ , and the right side is $2$ exactly when $h = (s^2 - 2)/(2s)$ . None of this used rationality. What is new is only that $s$ now exists.

Before reading on: which line of the proof uses the axiom, and what would that line say over $\mathbb{Q}$ ?

Proof. Let $S \mathrel{:=} \{ x \in \mathbb{R} : x > 0, \ x^2 < 2 \}$ . By Example (A set of reals that must have a supremum), $S$ is nonempty (it contains $1$ ) and bounded above by $2$ , so by Axiom 1.3.1 its supremum $s \mathrel{:=} \sup S$ exists, and $1 \le s \le 2$ . In particular $s > 0$ and $s^2 \ge 1$ . Throughout we use Theorem 1.1.2 (g): for $u, v \ge 0$ , $u < v$ if and only if $u^2 < v^2$ .

Case 1: $s^2 < 2$ . Let $h \mathrel{:=} \frac{2 - s^2}{4s + 2},$ which depends only on $s$ . Then $h > 0$ , because $2 - s^2 > 0$ and $4s + 2 > 0$ . Also $h \le \tfrac16$ , because $2 - s^2 \le 1$ and $4s + 2 \ge 6$ . Hence $h \le 1$ , and multiplying by $h > 0$ gives $h^2 \le h$ . Therefore $\begin{aligned} (s + h)^2 &= s^2 + 2sh + h^2 \le s^2 + (2s + 1)h \\ &= s^2 + \tfrac{2 - s^2}{2} = 1 + \tfrac{s^2}{2} < 2, \end{aligned}$ where the last inequality holds because $s^2 < 2$ . Also $s + h > 0$ . Hence $s + h \in S$ . But $s + h > s$ , which contradicts (S1), that $s$ is an upper bound of $S$ . So Case 1 is impossible.

Case 2: $s^2 > 2$ . Let $h \mathrel{:=} \frac{s^2 - 2}{2s},$ which is defined and positive because $s > 0$ and $s^2 > 2$ . Then $s - h = (s^2 + 2)/(2s) > 0$ , and $(s - h)^2 = s^2 - 2sh + h^2 = 2 + h^2 > 2 .$ We claim that $s - h$ is an upper bound of $S$ . Let $x \in S$ and suppose $x > s - h$ . Since $s - h > 0$ , we get $x^2 > (s - h)^2 > 2$ , contradicting $x^2 < 2$ . Hence $x \le s - h$ for every $x \in S$ . Then (S2) gives $s \le s - h$ , which is false since $h > 0$ . So Case 2 is impossible.

By trichotomy, $s^2 = 2$ . For uniqueness, let $t > 0$ with $t^2 = 2$ . If $t < s$ , then $t^2 < s^2$ , and if $s < t$ , then $s^2 < t^2$ ; both contradict $t^2 = 2 = s^2$ . Hence $t = s$ . This proves the theorem.

We write $\sqrt{2}$ for this number. By Logic and Proof, Theorem 2.2.1 it is not rational, so $\mathbb{R} \ne \mathbb{Q}$ : irrational numbers exist.

Compare this proof with the one of Theorem 1.2.2. The two computations with $h$ are the same, word for word: they are ordered-field algebra, and for a rational $s$ both values of $h$ are rational. What changed is a single line. In $\mathbb{Q}$ there was no $s$ to start from: the argument showed that no rational number can be the supremum, since its square cannot be less than $2$ , more than $2$ , or equal to $2$ . In $\mathbb{R}$ the axiom supplies $s$ , and the very same argument now shows that its square can only be $2$ .

The proof is an instance of a move this book uses again and again.

To construct a point: collect the points where “things are still fine” into a set, take its supremum, and rule out each way the supremum could fail to be the point you want.

Here “things are still fine” meant $x^2 < 2$ . The exercises of this section and of the last section of the chapter ask you to run the move yourself, with less and less of the proof given. In Chapter 6 the Intermediate Value Theorem is proved the same way: the point where a continuous function crosses zero is the supremum of the points where it is still negative. In Chapter 4 the Heine–Borel theorem takes the supremum of the points $x$ for which $[a, x]$ is still covered by finitely many of the given open sets.

1.6.2. Roots of every order

The template does not care that the exponent is $2$ or that the number is $2$ . Only the choice of $h$ needs new work.

Theorem 1.6.2 (Existence of Roots)

Let $a > 0$ and $n \in \mathbb{Z}_{>0}$ . There is exactly one real number $s > 0$ with $s^n = a$ .

We write this number $a^{1/n}$ , or $\sqrt[n]{a}$ . For $a = 0$ the only real $s \ge 0$ with $s^n = 0$ is $s = 0$ (a product of positive numbers is positive), so we also set $\sqrt[n]{0} \mathrel{:=} 0$ ; every $a \ge 0$ then has exactly one nonnegative $n$ -th root.

Idea. Take $S = \{ x > 0 : x^n < a \}$ and $s = \sup S$ , as before, and rule out $s^n < a$ and $s^n > a$ . The new difficulty is the estimate. For $n = 2$ we expanded $(s + h)^2$ and bounded $h^2$ by $h$ . For general $n$ , expanding $(s + h)^n$ is messy. We work backwards from what we need instead.

We need $(s + h)^n - s^n < a - s^n$ . A difference of $n$ -th powers factors: $y^n - x^n = (y - x)\bigl( y^{n-1} + y^{n-2} x + \dots + x^{n-1} \bigr).$ With $y = s + h$ and $x = s$ , the first factor is $h$ , which we control. The second factor is a sum of $n$ terms, each at most $(s + h)^{n-1}$ . That still depends on $h$ , and we cannot solve for $h$ while $h$ is on both sides. So we bound it by something a little bigger: if $h < 1$ , each term is at most $(s + 1)^{n-1}$ . This gives $(s + h)^n - s^n \le h \cdot C, \qquad C \mathrel{:=} n (s + 1)^{n-1} .$ The point is that $C$ depends only on $n$ and $s$ , and not on $h$ . Now it suffices to have $hC < a - s^n$ , and $h = (a - s^n)/(2C)$ does it, with a factor $\tfrac12$ to make the inequality strict. We needed $h < 1$ along the way, so we cap $h$ at $\tfrac12$ .

For $s - h$ the same factorization gives $s^n - (s - h)^n \le h \cdot n s^{n-1} \le hC$ , so the same $C$ , and the same $h$ , serve both cases.

Proof. We first prove a power estimate.

Claim. Let $0 \le x < y$ and $k \in \mathbb{Z}_{>0}$ . Then $x^k < y^k$ : the map $x \mapsto x^k$ is strictly increasing on $[0, \infty)$ . Consequently $x^m \le y^m$ for every integer $m \ge 0$ , where $u^0 \mathrel{:=} 1$ . Moreover $0 < y^k - x^k \le k y^{k-1} (y - x).$

Proof of Claim. Powers are defined by recursion (Sets, Relations, and Cardinality, Chapter 2): $u^0 \mathrel{:=} 1$ and $u^{k+1} \mathrel{:=} u^k u$ , so that $u^1 = u$ ; here only $k \ge 1$ is needed.

We first show $0 \le x^k < y^k$ by induction on $k$ . For $k = 1$ this is the hypothesis. If $0 \le x^k < y^k$ , then $x^{k+1} = x^k x \ge 0$ , and $x^{k+1} = x^k x \le x^k y < y^k y = y^{k+1},$ where the first step multiplies $x < y$ by $x^k \ge 0$ (Theorem 1.1.2 (c), or equality if $x^k = 0$ ) and the second multiplies $x^k < y^k$ by $y > 0$ . This proves the first statement, and the second follows, since for $m = 0$ both sides are $1$ .

For the estimate, write $\Sigma \mathrel{:=} \sum_{j=0}^{k-1} y^j x^{k-1-j}$ . Multiplying out, $\begin{aligned} (y - x)\Sigma &= \sum_{j=0}^{k-1} y^{j+1} x^{k-1-j} - \sum_{j=0}^{k-1} y^j x^{k-j} \\ &= y^k - x^k, \end{aligned}$ since every other term appears once in each sum and cancels. Each term of $\Sigma$ satisfies $0 \le y^j x^{k-1-j} \le y^j y^{k-1-j} = y^{k-1}$ , by the second statement with $m = k - 1 - j$ , multiplied by $y^j > 0$ ; and the term with $j = k - 1$ equals $y^{k-1} > 0$ . Hence $0 < \Sigma \le k y^{k-1}$ . Multiplying by $y - x > 0$ gives the claim.

Let $S \mathrel{:=} \{ x \in \mathbb{R} : x > 0, \ x^n < a \}$ .

$S$ is nonempty. Let $x_0 \mathrel{:=} a/(1 + a)$ . Then $0 < x_0 < 1$ and $x_0 < a$ . Since $0 < x_0 < 1$ , multiplying by $x_0$ repeatedly gives $x_0^n \le x_0$ (by induction on $n$ ). Hence $x_0^n \le x_0 < a$ , and $x_0 \in S$ .

$S$ is bounded above by $1 + a$ . If $x \ge 1 + a$ , then $x \ge 1$ , so $x^n \ge x$ (again by induction on $n$ ), and $x^n \ge 1 + a > a$ . So $x \notin S$ .

By Axiom 1.3.1, $s \mathrel{:=} \sup S$ exists, and $s \ge x_0 > 0$ . Let $C \mathrel{:=} n (s + 1)^{n-1},$ which depends only on $n$ and $s$ . Suppose $s^n \ne a$ , and let $h \mathrel{:=} \min\Bigl\{ \frac12, \ \frac{\left| s^n - a \right|}{2C} \Bigr\} > 0 .$ Then $hC \le \tfrac12 \left| s^n - a \right| < \left| s^n - a \right|$ .

Case 1: $s^n < a$ . Apply the claim with $k = n$ , $x = s$ , and $y = s + h$ . Since $s + h < s + 1$ , the claim with $m = n - 1$ gives $(s + h)^{n-1} \le (s + 1)^{n-1}$ (both sides are $1$ when $n = 1$ ). Therefore $(s + h)^n - s^n \le n (s + h)^{n-1} h \le C h < a - s^n ,$ so $(s + h)^n < a$ . Hence $s + h \in S$ , although $s + h > s$ . This contradicts that $s$ is an upper bound of $S$ .

Case 2: $s^n > a$ . First, $s - h > 0$ . Indeed $(s + 1)^{n-1} \ge s^{n-1}$ by the claim with $m = n - 1$ (both sides are $1$ when $n = 1$ ), so $h \le \frac{s^n - a}{2C} < \frac{s^n}{2C} \le \frac{s^n}{2 n s^{n-1}} = \frac{s}{2n} < s .$ Apply the claim with $k = n$ , $x = s - h$ , and $y = s$ : $s^n - (s - h)^n \le n s^{n-1} h \le C h < s^n - a ,$ so $(s - h)^n > a$ . Now $s - h$ is an upper bound of $S$ : if $x \in S$ had $x > s - h$ , the claim would give $x^n > (s - h)^n > a$ , contradicting $x \in S$ . But $s - h < s$ , which contradicts that $s$ is the least upper bound.

Both cases are impossible, so $s^n = a$ by trichotomy. If also $t > 0$ and $t^n = a$ , then $t = s$ , since $t < s$ or $s < t$ would give $t^n \ne s^n$ by the claim. This proves the theorem.

For $n = 2$ and $a = 2$ the constant is $C = 2(s + 1)$ , slightly larger than the $2s + 1$ that the direct expansion gave. The general proof pays for its generality with a cruder bound. We never needed a good bound, only one that does not depend on $h$ .

Example (Locating a cube root)

Show that $1.25 < \sqrt[3]{2} < 1.26$ .

Solution. By Theorem 1.6.2, $s \mathrel{:=} \sqrt[3]{2}$ exists and $s^3 = 2$ . Exact arithmetic gives $1.25^3 = 1.953125 < 2 < 2.000376 = 1.26^3 .$ The claim in the proof of Theorem 1.6.2 says that $x \mapsto x^3$ is strictly increasing on $[0, \infty)$ . If $s \le 1.25$ , then $s^3 \le 1.25^3 < 2$ ; and if $s \ge 1.26$ , then $s^3 \ge 1.26^3 > 2$ . Both contradict $s^3 = 2$ , so $1.25 < s < 1.26$ .

Remark. With $n$ -th roots we can define $a^{m/n} \mathrel{:=} (a^{1/n})^m$ for $a > 0$ , and check that the usual exponent laws hold for rational exponents. The powers $a^x$ with irrational $x$ wait for the exponential function, which Chapter 10 builds from power series.

1.6.3. The integer part of a real number

Before asking where the rationals are, we need to locate every real number between two consecutive integers. This sounds like school arithmetic, and it is. But its proof uses both the Archimedean property and well-ordering, and in $\mathbb{R}(x)$ it fails for the element $x$ (Exercise (C1: Exit check: the Archimedean property, and a circular proof)).

Lemma 1.6.3 (Integer Part)

For every $y \in \mathbb{R}$ there is exactly one integer $m$ with $m \le y < m + 1$ .

This integer is the integer part or floor of $y$ , written $\left\lfloor y \right\rfloor$ . For instance $\left\lfloor 2.7 \right\rfloor = 2$ and $\left\lfloor -2.7 \right\rfloor = -3$ .

Idea. Picture the integers as marks spaced $1$ apart. The Archimedean property puts a mark to the right of $y$ , and a mark to the left of $y$ . Among the marks to the right, well-ordering picks out the first one; the mark just before it is $\left\lfloor y \right\rfloor$ . Well-ordering is a statement about subsets of $\mathbb{N}$ , so we shift the marks so that they start at $0$ .

Proof. Existence. Let $y \in \mathbb{R}$ . By Theorem 1.5.1, there is $p \in \mathbb{N}$ with $p > -y$ , and there is $j \in \mathbb{N}$ with $j > y + p$ . Hence the set $T \mathrel{:=} \{ j \in \mathbb{N} : j - p > y \}$ is nonempty. By well-ordering (Sets, Relations, and Cardinality, Chapter 2), $T$ has a least element $j_0$ . Let $m \mathrel{:=} j_0 - p - 1$ , an integer because differences of integers are integers (the remark on $\mathbb{N}$ in the previous section). Then $m + 1 = j_0 - p > y$ , since $j_0 \in T$ . It remains to show $m \le y$ . First, $0 - p = -p < y$ by the choice of $p$ , so $0 \notin T$ and $j_0 \ne 0$ . Hence $j_0 \ge 1$ (Example (Every nonzero natural number is at least 1)), so $j_0 - 1 \in \mathbb{N}$ (again from that remark), and $j_0 - 1 \notin T$ because it is smaller than the least element of $T$ . So $(j_0 - 1) - p \le y$ , that is, $m \le y$ .

Uniqueness. Suppose $m$ and $m'$ are integers with $m \le y < m + 1$ and $m' \le y < m' + 1$ , and suppose $m < m'$ . Then $m' - m$ is a positive integer, hence a nonzero natural number (the remark on $\mathbb{N}$ in the previous section), so $m' - m \ge 1$ by Example (Every nonzero natural number is at least 1); that is, $m' \ge m + 1$ . Hence $y \ge m' \ge m + 1 > y$ , a contradiction. By symmetry $m' < m$ is impossible too, so $m = m'$ .

1.6.4. The rationals are dense

We know now that irrational numbers exist. How are they arranged among the rationals? Could there be a whole interval with no rational number in it? No: every interval, however short, contains a rational.

Theorem 1.6.4 (Density of the Rationals)

Let $x, y \in \mathbb{R}$ with $x < y$ . There is $q \in \mathbb{Q}$ with $x < q < y$ .

Idea. Think of a ruler whose marks are the fractions $k/n$ , spaced $1/n$ apart. If the spacing is smaller than the gap $y - x$ , the ruler cannot jump over the interval $(x, y)$ : the first mark to the right of $x$ is at most one step past $x$ , and so it lands before $y$ .

$Diagram. Labels: x, y, tfrac 1n, tfrac m-1n, tfrac mn$

The plan: ① choose $n$ with $1/n < y - x$ , by the Archimedean property; ② let $m/n$ be the first mark strictly to the right of $x$ , that is, $m = \left\lfloor nx \right\rfloor + 1$ ; ③ check that $m/n < y$ .

Proof. Let $x < y$ . Then $y - x > 0$ , so by Corollary 1.5.2 there is $n \in \mathbb{Z}_{>0}$ with $1/n < y - x$ ; the $n$ depends on $x$ and $y$ , through $y - x$ . By Lemma 1.6.3, let $m \mathrel{:=} \left\lfloor nx \right\rfloor + 1$ , an integer, since sums of integers are integers (the remark on $\mathbb{N}$ in the previous section). Then $m - 1 \le nx < m$ . Therefore $nx < m \le nx + 1 < nx + n(y - x) = ny ,$ where the last inequality uses $1 < n(y - x)$ , which is $1/n < y - x$ multiplied by $n > 0$ . Dividing by $n > 0$ gives $x < m/n < y$ . Since $m \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ , $q \mathrel{:=} m/n$ is rational. This proves the theorem.

Example (Running the proof)

Follow the proof of Theorem 1.6.4 to find a rational number between $\sqrt{2}$ and $\tfrac32$ .

Solution. Step ①: the spacing. We need $1/n < \tfrac32 - \sqrt{2}$ , that is, $\sqrt{2} < \tfrac32 - \tfrac1n$ . By Theorem 1.1.2 (g), applied to the positive numbers $\sqrt{2}$ and $\tfrac32 - \tfrac1n$ , this holds exactly when $2 < (\tfrac32 - \tfrac1n)^2$ . For $n = 12$ , $\tfrac32 - \tfrac1{12} = \tfrac{17}{12}$ and $(\tfrac{17}{12})^2 = \tfrac{289}{144} > \tfrac{288}{144} = 2$ , so $n = 12$ works. (For $n = 11$ , $(\tfrac{31}{22})^2 = \tfrac{961}{484} < 2$ , so $12$ is the least $n$ that works, but any $n \ge 12$ would do.)

Step ②: the first mark past $x$ . We need $\left\lfloor 12\sqrt{2} \right\rfloor$ . Since $16^2 = 256 \le 288 = (12\sqrt{2})^2 < 289 = 17^2$ , Theorem 1.1.2 (g) gives $16 \le 12\sqrt{2} < 17$ , so $\left\lfloor 12\sqrt{2} \right\rfloor = 16$ and $m = 17$ .

Step ③: the answer. The proof guarantees $\sqrt{2} < \tfrac{17}{12} < \tfrac32$ . Directly: $(\tfrac{17}{12})^2 = \tfrac{289}{144} > 2$ gives the left inequality, and $\tfrac{17}{12} < \tfrac{18}{12}$ gives the right one.

The irrationals are just as widely spread. The trick is to shift the rationals by $\sqrt{2}$ .

Corollary 1.6.5

Let $x, y \in \mathbb{R}$ with $x < y$ . There is an irrational number $z$ with $x < z < y$ .

Proof. Since $x - \sqrt{2} < y - \sqrt{2}$ , Theorem 1.6.4 gives $q \in \mathbb{Q}$ with $x - \sqrt{2} < q < y - \sqrt{2}$ . Let $z \mathrel{:=} q + \sqrt{2}$ . Then $x < z < y$ . If $z$ were rational, then $\sqrt{2} = z - q$ would be a difference of rationals, hence rational, contradicting Logic and Proof, Theorem 2.2.1. So $z$ is irrational.

This is why the existence of $\sqrt{2}$ came first in this section: the proof of Corollary 1.6.5 needs one irrational number to shift by, and Theorem 1.6.1 supplies it.

Quick check. Name a rational number between $\sqrt{2}$ and $1.415$ , and an irrational number between $0$ and $10^{-6}$ . Justify both.

Solution. Rational: $1.4143$ . Its square is $2.00024449 > 2$ , so $1.4143 > \sqrt{2}$ by Theorem 1.1.2 (g), and $1.4143 < 1.415$ .

Irrational: $z \mathrel{:=} \sqrt{2} \cdot 10^{-7}$ . Since $1 < \sqrt{2} < 2$ , we get $0 < z < 2 \cdot 10^{-7} < 10^{-6}$ . If $z$ were rational, then $\sqrt{2} = 10^7 z$ would be rational, contradicting Logic and Proof, Theorem 2.2.1.

Warning. “Dense” does not mean “next to each other”. There is no smallest positive rational number and no “next rational after $0$ ”: if $q > 0$ is rational, then $q/2$ is a smaller positive rational. The same holds for irrationals: if $z > 0$ is irrational, so is $z/2$ , and it is smaller. Between any two distinct rationals there are infinitely many more, and between any two distinct reals there are rationals and irrationals alike.

Density is what makes decimals, and more generally rational approximation, possible. Every real number can be pinned down by rationals from below as closely as we like (Exercise (B1: Every real number is a supremum of rationals)). In Metric and Topological Spaces the word dense becomes a notion in any metric space: a set that meets every ball. The rationals in the real line are the model example.

1.6.5. Exercises

A. Check your understanding

Exercise (A1)

True or false? Give a reason or a counterexample for each.

(a) There is a least positive irrational number.
(b) Between any two distinct rational numbers there is an irrational number.
(c) Between any two distinct irrational numbers there is a rational number.
(d) Every nonempty set of rationals that is bounded above has a supremum in $\mathbb{R}$ , and that supremum is rational.
(e) In the proof of Theorem 1.6.2, the constant $C$ depends on $h$ .
(f) Run Case 1 of the proof of Theorem 1.6.1 with the value $\frac75$ in place of $s$ (so $s^2 = \frac{49}{25} < 2$ ): compute $h$ , and check that $(s + h)^2 < 2$ . Which property of a supremum does this show $\frac75$ lacks?

Solution.

(a) False. If $z > 0$ is irrational, then $z/2$ is positive, smaller than $z$ , and irrational (if $z/2$ were rational, so would be $z = 2 \cdot (z/2)$ ).
(b) True, by Corollary 1.6.5 applied to the two rationals.
(c) True, by Theorem 1.6.4 applied to the two irrationals.
(d) False. The set $A \mathrel{:=} \{ x \in \mathbb{Q} : x > 0, \ x^2 < 2 \}$ is nonempty and bounded above by $2$ , so it has a supremum $s \in \mathbb{R}$ by Axiom 1.3.1. If $s$ were rational, it would be a rational upper bound of $A$ that is at most every real upper bound, and in particular at most every rational one. So $s$ would be a supremum of $A$ in $\mathbb{Q}$ , contradicting Theorem 1.2.2. (In fact $s = \sqrt{2}$ .)
(e) False. $C = n(s + 1)^{n-1}$ depends only on $n$ and $s$ . It has to be independent of $h$ , because $h$ is then chosen in terms of $C$ .
(f) Here $2 - s^2 = \frac1{25}$ and $4s + 2 = \frac{38}{5}$ , so $h = \frac{1/25}{38/5} = \frac1{190}$ and $s + h = \frac{267}{190}$ . Then $\Bigl( \frac{267}{190} \Bigr)^2 = \frac{71289}{36100} < \frac{72200}{36100} = 2 ,$ and the proof’s bound gives the same: $(s + h)^2 \le 1 + \frac{s^2}{2} = \frac{99}{50} < 2$ . So $\frac{267}{190} \in S$ and $\frac{267}{190} > \frac75$ : the number $\frac75$ is not an upper bound of $S$ , so it fails (S1). This is no contradiction, because nothing said that $\frac75$ was the supremum. In the proof the same computation contradicts (S1) for $s = \sup S$ .

B. Practice

Exercise (B1: Every real number is a supremum of rationals)

Let $x \in \mathbb{R}$ . Prove that $x = \sup \{ q \in \mathbb{Q} : q < x \}$ .

Solution. Let $A \mathrel{:=} \{ q \in \mathbb{Q} : q < x \}$ . By Theorem 1.6.4 applied to $x - 1 < x$ , there is a rational in $(x - 1, x)$ , so $A$ is nonempty. By definition every element of $A$ is less than $x$ , so $x$ is an upper bound of $A$ .

Let $\varepsilon > 0$ . By Theorem 1.6.4 applied to $x - \varepsilon < x$ , there is $q \in \mathbb{Q}$ with $x - \varepsilon < q < x$ . Then $q \in A$ and $q > x - \varepsilon$ . By Theorem 1.4.1, $x = \sup A$ .

Exercise (B2: The square root of three, finished)

Here is the start of a proof that there is exactly one real $s > 0$ with $s^2 = 3$ .

Let $S \mathrel{:=} \{ x \in \mathbb{R} : x > 0, \ x^2 < 3 \}$ . Then $1 \in S$ , and if $x \ge 2$ , then $x^2 \ge 4 > 3$ ; so $S$ is nonempty and bounded above by $2$ . By Axiom 1.3.1, $s \mathrel{:=} \sup S$ exists, and $s \ge 1$ .

Case $s^2 < 3$ . Let $h \mathrel{:=} (3 - s^2)/(4s + 2)$ . Then $h > 0$ . Since $3 - s^2 \le 2$ and $4s + 2 \ge 6$ , we have $h \le \frac13$ , so $h^2 \le h$ , and $(s + h)^2 \le s^2 + (2s + 1)h = \frac{3 + s^2}{2} < 3$ . Hence $s + h \in S$ , and $s + h > s$ contradicts (S1).

Case $s^2 > 3$ . $\ldots$

Name the move, then complete it. Give an explicit $h$ for the second case and check that it works; then finish the proof, including uniqueness.

Solution. The move is construct a point as a supremum: the points where “things are still fine” ( $x^2 < 3$ ) form $S$ , the axiom supplies $s = \sup S$ , and each way $s$ could fail ( $s^2 < 3$ , $s^2 > 3$ ) is ruled out. The given text rules out the first; the missing step rules out the second, against (S2) this time.

Case $s^2 > 3$ . Let $h \mathrel{:=} (s^2 - 3)/(2s)$ , which is defined and positive because $s \ge 1$ and $s^2 > 3$ . Then $s - h = (s^2 + 3)/(2s) > 0$ and $(s - h)^2 = s^2 - 2sh + h^2 = 3 + h^2 > 3 .$ If some $x \in S$ had $x > s - h$ , then, as $s - h > 0$ , Theorem 1.1.2 (g) would give $x^2 > (s - h)^2 > 3$ , which is impossible for $x \in S$ . So $s - h$ is an upper bound of $S$ , and (S2) gives $s \le s - h$ , which is false since $h > 0$ .

Both cases are impossible, so $s^2 = 3$ by trichotomy. For uniqueness, let $t > 0$ with $t^2 = 3$ . If $t < s$ or $s < t$ , then Theorem 1.1.2 (g) gives $t^2 < s^2$ or $s^2 < t^2$ , contradicting $t^2 = 3 = s^2$ . Hence $t = s$ .

Exercise (B3: The cube root of five)

Prove that there is exactly one real $s > 0$ with $s^3 = 5$ . Hence show that $1.70 < s < 1.71$ .

Solution. By Theorem 1.6.2 with $a = 5$ and $n = 3$ , there is exactly one $s > 0$ with $s^3 = 5$ .

Exact arithmetic gives $1.70^3 = 4.913 < 5$ and $1.71^3 = 5.000211 > 5$ . By the claim in the proof of Theorem 1.6.2, $x \mapsto x^3$ is strictly increasing on $[0, \infty)$ . If $s \le 1.70$ , then $s^3 \le 4.913 < 5$ ; if $s \ge 1.71$ , then $s^3 \ge 5.000211 > 5$ . Both contradict $s^3 = 5$ , so $1.70 < s < 1.71$ .

C. Going deeper

Exercise (C1: Exit check: the square root of two, in both fields)

(a) Prove that there is a real number $s > 0$ with $s^2 = 2$ .
(b) Prove that the set $\{ x \in \mathbb{Q} : x > 0, \ x^2 < 2 \}$ has no supremum in $\mathbb{Q}$ .
(c) Both proofs use the same two values of $h$ . Explain in two or three sentences why the same computation yields an existence theorem in $\mathbb{R}$ and a nonexistence theorem in $\mathbb{Q}$ .

Solution.

(a) This is Theorem 1.6.1. Let $S \mathrel{:=} \{ x \in \mathbb{R} : x > 0, \ x^2 < 2 \}$ ; it contains $1$ and is bounded above by $2$ , so $s \mathrel{:=} \sup S$ exists by Axiom 1.3.1, and $s \ge 1$ . If $s^2 < 2$ , then $h \mathrel{:=} (2 - s^2)/(4s + 2)$ satisfies $0 < h \le \tfrac16$ , so $h^2 \le h$ and $(s + h)^2 \le s^2 + (2s + 1)h = 1 + s^2/2 < 2$ , and $s + h \in S$ exceeds the upper bound $s$ : impossible. If $s^2 > 2$ , then $h \mathrel{:=} (s^2 - 2)/(2s)$ satisfies $s - h = (s^2 + 2)/(2s) > 0$ and $(s - h)^2 = 2 + h^2 > 2$ ; every $x \in S$ then satisfies $x \le s - h$ , since $x > s - h$ would give $x^2 > 2$ . So $s - h < s$ is an upper bound, contradicting (S2). By trichotomy $s^2 = 2$ .
(b) Let $A \mathrel{:=} \{ x \in \mathbb{Q} : x > 0, \ x^2 < 2 \}$ , and suppose $r \in \mathbb{Q}$ is a supremum of $A$ in $\mathbb{Q}$ , that is, a rational upper bound of $A$ that is at most every rational upper bound. As $1 \in A$ , $r \ge 1$ . By Logic and Proof, Theorem 2.2.1, $r^2 \ne 2$ .

If $r^2 < 2$ , let $h \mathrel{:=} (2 - r^2)/(4r + 2)$ . This is rational, and the computation of (a) gives $(r + h)^2 < 2$ . So $r + h \in A$ and $r + h > r$ , contradicting that $r$ is an upper bound.

If $r^2 > 2$ , let $h \mathrel{:=} (r^2 - 2)/(2r)$ . Then $r - h = (r^2 + 2)/(2r)$ is rational and positive, with $(r - h)^2 = 2 + h^2 > 2$ . As in (a), every $x \in A$ satisfies $x \le r - h$ , so $r - h$ is a rational upper bound of $A$ smaller than $r$ , contradicting the choice of $r$ .

Both cases are impossible, so $A$ has no supremum in $\mathbb{Q}$ .
(c) The computation shows, in any ordered field, that a supremum of the set cannot have square less than $2$ or greater than $2$ . In $\mathbb{R}$ the axiom guarantees that a supremum exists, so its square must be $2$ : existence. In $\mathbb{Q}$ no element has square $2$ (Logic and Proof, Theorem 2.2.1), so no case is left, and no supremum can exist. For rational $r$ the values of $h$ are rational, which is why the argument stays inside $\mathbb{Q}$ .

Marking scheme. (10 points) - 1: (a) defines $S$ , checks that it is nonempty and bounded above, and takes $s = \sup S$ from Axiom 1.3.1. - 2: (a) rules out $s^2 < 2$ with an explicit $h > 0$ , verifying $(s + h)^2 < 2$ including any side condition such as $h \le 1$ , and contradicts (S1). - 2: (a) rules out $s^2 > 2$ with an explicit $h > 0$ , verifying $s - h > 0$ and that $s - h$ is an upper bound, and contradicts (S2). - 1: (b) supposes a rational supremum $r$ and excludes $r^2 = 2$ by Logic and Proof, Theorem 2.2.1. - 2: (b) in each case checks that the new number is rational and derives the contradiction with “upper bound in $\mathbb{Q}$ ” or “least among rational upper bounds”. - 2: (c) says that the computation excludes $s^2 < 2$ and $s^2 > 2$ in any ordered field, that in $\mathbb{R}$ the axiom supplies $s$ so $s^2 = 2$ remains, and that in $\mathbb{Q}$ nothing remains. Fatal errors (0 for the step): using $\sqrt 2$ to define $S$ or $h$ ; asserting $s + h \in S$ or $(s - h)^2 > 2$ without the computation; an $h$ that depends on an element of $S$ rather than on $s$ alone. A proof with a different $h$ (for instance $h = \min\{ 1, (2 - s^2)/6 \}$ in Case 1, using $2s + 1 \le 5$ ) earns full marks if its bound is verified.

Exercise (C2: Dyadic rationals)

A dyadic rational is a number of the form $m/2^k$ with $m \in \mathbb{Z}$ and $k \in \mathbb{N}$ . Prove that between any two real numbers $x < y$ there is a dyadic rational.

Hint: compare $2^k$ with $k$ .

Solution. First, $2^k > k$ for every $k \in \mathbb{N}$ , by induction (Logic and Proof, Axiom 4.2.1; Logic and Proof, Exercise (B1) even gives $2^k \ge k + 1$ ): $2^0 = 1 > 0$ , and if $2^k > k$ , then $2^{k+1} = 2^k + 2^k > k + 1$ , since $2^k \ge 1$ .

Let $x < y$ . By Corollary 1.5.2 there is $k \in \mathbb{Z}_{>0}$ with $1/k < y - x$ ; the $k$ depends on $y - x$ . Then $1/2^k < 1/k < y - x$ . By Lemma 1.6.3, let $m \mathrel{:=} \left\lfloor 2^k x \right\rfloor + 1$ . Then $m - 1 \le 2^k x < m$ , and $2^k x < m \le 2^k x + 1 < 2^k x + 2^k (y - x) = 2^k y ,$ using $1 < 2^k (y - x)$ . Dividing by $2^k > 0$ gives $x < m/2^k < y$ .

The proof is that of Theorem 1.6.4 with the ruler of step $1/n$ replaced by one of step $1/2^k$ . Only the choice of step size changed; any family of steps that can be made smaller than every $\varepsilon > 0$ would do.

Exercise (C3: Find the faulty line)

A student proves Theorem 1.6.4 as follows. Let $x < y$ .

(1) Let $R \mathrel{:=} \{ r \in \mathbb{Q} : r > x \}$ . By Theorem 1.5.1 some natural number exceeds $x$ , so $R$ is nonempty.
(2) By well-ordering, $R$ has a least element $q$ .
(3) By Corollary 1.5.2, choose $n \in \mathbb{Z}_{>0}$ with $1/n < y - x$ .
(4) Since $q - 1/n$ is rational and smaller than the least element $q$ of $R$ , it is not in $R$ . So $q - 1/n \le x$ , and hence $q \le x + 1/n < y$ .
(5) Therefore $q \in \mathbb{Q}$ and $x < q < y$ .

Is the statement the student is proving true? Does the argument prove it? Find the line that fails and say why. Show that for $x = 0$ the set $R$ has no least element. Then repair the proof by changing $R$ so that the faulty line becomes correct.

Solution. The statement is true: it is Theorem 1.6.4. So there is no counterexample to the conclusion, and the only question is whether the argument proves it. It does not.

Line (2) fails. Well-ordering says that a nonempty subset of $\mathbb{N}$ has a least element. The set $R$ is a set of rationals, not of natural numbers, and it need not have a least element. For $x = 0$ , $R$ is the set of positive rationals; if $q \in R$ , then $q/2 \in R$ and $q/2 < q$ . So no element of $R$ is least. Lines (3)–(5) are correct once a least element is available.

Repair. Fix $n$ first, as in line (3), and replace $R$ by a set of integers: $R_n \mathrel{:=} \{ m \in \mathbb{Z} : m/n > x \}$ . By Lemma 1.6.3, its least element is $m \mathrel{:=} \left\lfloor nx \right\rfloor + 1$ : indeed $m/n > x$ , while $(m - 1)/n \le x$ . Now line (4) holds with $q \mathrel{:=} m/n$ : since $(m - 1)/n = q - 1/n \le x$ , we get $q \le x + 1/n < y$ . This is the proof of Theorem 1.6.4. The point is that the step $1/n$ is fixed first, so the candidates $m/n$ form a copy of the integers, where “least” makes sense.