Chapter 08 Additional Topics

8.6 A Construction of $\mathbf{R}$ From $\mathbf{Q}$

Theorem 8.6.1 (Existence of the Real Numbers).

There exists an ordered field in which every nonempty set that is bounded above has a least upper bound. In addition, this field contains $\mathbf{Q}$ as a subfield.

Axiom of Completeness.

Every nonempty set of real numbers that is bounded above has a least upper bound.

Dedekind Cuts

Definition 8.6.2.

A subset $A$ of the rational numbers is called a cut if it possesses the following three properties:

(c1) $A \not = \emptyset$ and $A \not = \mathbf{Q}$.

(c2) if $r \in A$, then $A$ also contains every rational $q < r$.

(c3) $A$ does not have a maximum; that is, if $r ∈ A$, then there exists $s ∈ A$ with $r < s$.

Exercise 8.6.1.

(a) Fix $r ∈ \mathbf{Q}$. Show that the set $C_r = \{ t ∈ \mathbf{Q} : t < r \}$ is a cut.

Proof:

(c1) $t \in C_r$ so it's not emptyset. $r \not \in C_r$, so it's not $\mathbf{Q}$.

(c2) If $t \in C_r$, and $s < t$, so $s < r$, so $s \in C_r$.

(c3) If $t \in C_r$, then $t < r$, we can find $t < s < r$, also $s \in C_r$.

$\square$

The temptation to think of all cuts as being of this form should be avoided. Which of the following subsets of $\mathbf{Q}$ are cuts?

(b) $S= \{t ∈ \mathbf{Q} : t ≤ 2\}$

Solution: No. $S$ has a maximum, i.e. $2$.

(c) $T = \{t ∈ \mathbf{Q} : t^2 < 2 \text{ or } t < 0\}$

Solution: Yes.

(d) $U = \{t ∈ \mathbf{Q} : t^2 \leq 2 \text{ or } t < 0\}$

Solution: Yes.

Exercise 8.6.2.

Let $A$ be a cut. Show that if $r ∈ A$ and $s \not ∈ A$, then $r < s$.

Proof: If $s = r$, then $s \in A$. If $s < r$, then $s \in A$. So $r < s$.

$\square$

Definition 8.6.3.

Define the real numbers $\mathbf{R}$ to be the set of all cuts in $\mathbf{Q}$.

Field and Order Properties

Given a set $F$ and two elements $x,y ∈ F$, an operation on $F$ is a function that takes the ordered pair $(x,y)$ to a third element $z ∈ F$. Writing $x + y$ or $xy$ to represent different operations reminds us of the two operations that we are trying to emulate.

Definition 8.6.4.

A set $F$ is a field if there exist two operations—addition $(x+y)$ and multiplication $(xy)$—that satisfy the following list of conditions:

(f1) (commutativity) $x+y= y +x$ and $xy= yx$ for all $x,y ∈ F$.

(f2) (associativity)$(x+y)+z = x+(y+z)$ and $(xy)z = x(yz)$ for all $x,y,z ∈ F$.

(f3) (identities exist) There exist two special elements $0$ and $1$ with $0 \not = 1$ such that $x+0 = x$ and $x1 = x$ for all $x ∈ F$.

(f4) (inverses exist) Given $x ∈ F$, there exists an element $−x ∈ F$ such that $x+(−x) = 0$. If $x \not = 0$, there exists an element $x^{−1}$ such that $xx^{−1} = 1$.

(f5) (distributive property) $x(y +z) = xy +xz$ for all $x,y,z ∈ F$.

Exercise 8.6.3.

Using the usual definitions of addition and multiplication, determine which of these properties are possessed by $\mathbf{N}$, $\mathbf{Z}$, and $\mathbf{Q}$, respectively.

Solution:

$\mathbf{N}$: f1, f2, f5

$\mathbf{Z}$: f1, f2, f3, f5

$\mathbf{Q}$: f1, f2, f3, f4, f5

Definition 8.6.5.

An ordering on a set $F$ is a relation, represented by $≤$, with the following three properties:

(o1) For arbitrary $x,y ∈ F$, at least one of the statements $x ≤ y$ or $y ≤ x$ is true.

(o2) If $x ≤ y$ and $y ≤ x$, then $x = y$.

(o3) If $x ≤ y$ and $y ≤ z$, then $x ≤ z$.

A field $F$ is called an ordered field if $F$ is endowed with an ordering $≤$ that satisfies

(o4) If $y ≤ z$, then $x+y ≤ x+z$.

(o5) If $x ≥ 0$ and $y ≥ 0$, then $xy ≥ 0$.

Define $A ≤ B$ to mean $A ⊆ B$.

Exercise 8.6.4.

Show that this defines an ordering on $\mathbf{R}$ by verifying properties (o1), (o2), and (o3) from Definition 8.6.5.

Proof:

Let $r_1, r_2 \in \mathbf{R}$, if for every rational number $s \in r_1$ we have $s \in r_2$, then $r_1 \subseteq r_2$, i.e. $r_1 \leq r_2$.

Now assume $s \in r_1$ but $s \not \in r_2$. From exercise 8.6.2, since $r_1$ is not empty, then for every rational number $t \in r_2$, we know $t < s$. That means $t \in r_1$. So we have $r_2 \subseteq r_1$, i.e. $r2 \leq r_1$. We proved (o1).

$x \leq y$ means $x \subseteq y$, $y \leq x$ means $y \subseteq x$, So $x = y$. We proved (o2).

$x \leq y$ means $x \subseteq y$, $y \leq z$ means $y \subseteq z$, i.e. $x \leq z$. We proved (o3).

Algebra in $\mathbf{R}$

Given $A$ and $B$ in $\mathbf{R}$, define

$$A + B = \{a + b : a \in A \text{ and } b \in B\}$$

We first need to prove $A+B$ is a cut.

(c2) Let $a + b ∈ A + B$ be arbitrary and let $s ∈ \mathbf{Q}$ satisfy $s < a + b$.

Then, $s−b < a$, which implies that $s−b ∈ A$ because $A$ is a cut. But then

$$s = (s-b) + b \in A + B$$

Exercise 8.6.5.

(a) Show that (c1) and (c3) also hold for $A+B$. Conclude that $A+B$ is a cut.

Proof:

(c1) Since $A, B$ are cuts, then $A \not = \emptyset$ and $A \not = \mathbf{Q}$, $B \not = \emptyset$ and $B \not = \mathbf{Q}$

So $A+B$ cannot be empty.

Let $c \not \in A$, $d \not \in B$. We want to prove $c+d \not \in A+B$.

Assume otherwise, i.e. $c+d \in A+B$, that means we can find $a \in A, b \in B$, such that $a + b = c + d$. Then either $a \geq c$ or $b \geq d$.

If $a \geq c$, then $c \in A$, we have a contradiction. If $b \geq d$, then $d \in B$, we have a contradiction.

So $A+B \not = \mathbf{Q}$.

$\square$

(c3) Let $c \in A+B$, then $c = a + b$ for $a \in A$ and $b \in B$. Then we can find $e \in A$ and $f \in B$, such that

$$a < e, b < f$$

Then $e+f \in A+B$ and $a+b < e+f$.

$\square$

(b) Check that addition in $\mathbf{R}$ is commutative (f1) and associative (f2).

(f1) commutative

We want to prove $A+B = B+A$. We will first prove $A+B \leq B+A$. Assume $c = a+b \in A+B$, then $c = a+b = b+a \in B+A$. So $A+B \subseteq B+A$, i.e. $A+B \leq B+A$. For the same reason, $B+A \leq A+B$. Then with (o2), $A+B = B+A$.

(f2) associative

We want to prove $(A+B) + C = A + (B+C)$. We use the same strategy as (f1).

For any $d \in (A+B) + C$, then we know

$$d = (a+b) + c, a \in A, b \in B, c \in C$$

Then

$$d = (a+b) + c = a + (b+c) \in A + (B+C)$$

So $(A+B)+C \leq A + (B+C)$. For the same reason $A + (B+C) \leq (A+B) + C$. So $(A+B)+C = A + (B+C)$.

$\square$

(c) Show that property (o4) holds.

Proof:

(o4) states: if $B ≤ C$, then $A+B ≤ A+C$.

Assume $a+b \in A+B$, since $B \leq C$, then $b \in C$.

so $a+b \in A+C$, then $A+B \leq A+C$.

$\square$

(d) Show that the cut

$$O = \{p \in \mathbf{Q} : p < 0\}$$

successfully plays the role of the additive identity (f3). (Showing $A+O= A$ amounts to proving that these two sets are the same. The standard way to prove such a thing is to show two inclusions: $A + O ⊆ A$ and $A ⊆ A+O$.)

Proof:

Assume $a + o \in A+O$, since $o < 0$, $a + o < a$, so $a + o \in A$, then $A+O \subseteq A$.

Assume $a \in A$, we can $a < b \in A$, let $o = a - b < 0$, so $o \in O$. And $b + o = b + (a - b) = a$. So $a \in A + O$. Then $A \subseteq A + O$.

Then $A = A + O$.

$\square$

Given $A ∈ \mathbf{R}$, define

$$−A= \{r ∈ Q : \text{ there exists } t \not ∈ A \text{ with } t <−r \}.$$

Exercise 8.6.6.

(a) Prove that $−A$ defines a cut.

Proof:

(c1) We need to show $-A \not = \emptyset$ and $-A \not = \mathbf{Q}$.

Since $A \not = \mathbf{Q}$, so we can find $t \not \in A$. since $t < t + 1$, so $-(t+1) \in -A$. $-A$ is not an empty set.

Consider $-r \in A$ is a negative number, then $r$ is a positive number. If $r \in -A$, then there exists $t \not \in A$, and $t < -r$. But since $-r \in A$, we must have $t \in A$ based on (c2), so we have a contradiction. then $r \not \in -A$. So $-A \not = \mathbf{Q}$.

$\square$

(c2) We need to show if $r \in -A$, then $A$ also contains every rational $q < r$.

If $r \in -A$, and $q < r$, then $t < -r < -q$. so $q \in -A$.

$\square$

(c3) We need to show $-A$ does not have a maximum; that is, if $r ∈ -A$, then there exists $s ∈ -A$ with $r < s$.

Proof: Since $r \in -A$, then $t < -r$ and $t \not \in A$. Let $-s = \frac{t-r}{2}$, so $t < -s < -r$. Then $s \in -A$ and $r < s$.

$\square$

(b) What goes wrong if we set $−A= \{r ∈ Q :−r \not ∈ A\}$?

Solution: Take $A = C_2 = \{r ∈ Q : r < 2 \}$ as an example, then $-A = \{r ∈ Q : r \leq -2 \}$. Then $-2$ is the maximum of $-A$, then $-A$ cannot be a cut.

$\square$

(c) If $a ∈ A$ and $r ∈ −A$, show $a+r ∈ O$. This shows $A+(−A) ⊆ O$. Now, finish the proof of property (f4) for addition in Definition 8.6.4.

Proof:

If $r ∈ −A$, then $-r > t \not \in A$. From exercise 8.6.2, $a < t$. Then

$$a + r < t + r < -r + r = 0$$

So $a + r \in O$, i.e. $A+(-A) \subseteq O$, i.e. $A + (-A) \leq O$.

If $A = O$, then for $p \in O$, then $p < 0$, so $p/2 < 0$. Then $0 < -p/4 \not \in A$, so $p/2 \in -A$. Then $A + (-A) \supseteq O$.

If $O \subset A$, then $0 \in A$. let $p \in O$. So $p < 0$. Consider

$$0, -\frac{1}{2}p, -\frac{2}{2}p, \cdots$$

We can find $k$, such that $-\frac{k-1}{2}p \in A$, but $-\frac{k}{2}p \not \in A$. So $\frac{k+1}{2}p \in -A$. Then $-\frac{k}{2}p + \frac{k+1}{2}p = p$. So $A + (-A) \supseteq O$

If $A \subset O$, then $0 \not \in A$. Consider $p < 0$ and

$$0, \frac{1}{2}p, \frac{2}{2}p, \cdots$$

We can find $k$, such that $\frac{k-1}{2}p \not \in A$, but $\frac{k}{2}p \in A$. Now consider $-\frac{k-2}{2}p$, we have

$$-(-\frac{k-2}{2}p) = \frac{k-2}{2}p > \frac{k-1}{2}p \not \in A$$

So $-\frac{k-2}{2}p \in -A$. Also we have

$$-\frac{k-2}{2} p + \frac{k}{2} p = p$$

So $A + (-A) \supseteq O$.

In all 3 cases, we have $A + (-A) \supseteq O$.

In conclusion: $A + (-A) = O$. $\square$

Given $A ≥ O$ and $B ≥ O$ in $\mathbf{R}$, define the product

$$AB = \{ab : a ∈ A,b ∈ B \text{ with } a, b ≥ 0\} ∪ \{q ∈ Q : q < 0\}.$$

Exercise 8.6.7.

(a) Show that $AB$ is a cut and that property (o5) holds.

Proof:

(c1) $-1 \in AB$ so $AB$ is not empty.

Assume $c \not \in A, d \not \in B$, then $c \geq 0, d \geq 0$. Assume $cd \in AB$, then $cd \not \in \{q ∈ Q : q < 0\}$. So $cd \in \{ab : a ∈ A,b ∈ B \text{ with } a, b ≥ 0\}$

then we can find $ab = cd$. Since $0 \leq a < c, 0 \leq b < d$. We must have $ab < cd$.

So $AB \not = \mathbf{R}$.

(c2) If $A = O$ or $B = O$, then $\{ab : a ∈ A,b ∈ B \text{ with } a, b ≥ 0\}$ is empty, so $AB = \{q ∈ Q : q < 0\} = O$ which does not have a maximum.

If $A > O, B > O$, and $r \in AB$. If $r \leq 0$, we can find $0 < a \in A$ and $0 < b \in B$, then $ab > 0 \geq r$.

If $r > 0$, then $r = ab, a > 0, b > 0$. Since $A, B$ are all cuts, we can find $c > a, d > b$. Then $cd > ab$.

(c3) If $r \in AB$, and $s < r$. If $s < 0$, then $s \in AB$ by definition.

If $s \geq 0$, then $0 < r = ab$, where $a, b > 0$. Let $b' = s / a < r/a = b$, so $0 \leq b' \in B$. And $a b' = s \in AB$.

$\square$

(b) Propose a good candidate for the multiplicative identity (1) on $\mathbf{R}$ and show that this works for all cuts $A ≥ O$.

Proof:

Let $I = \{q \in \mathbf{Q}: q < 1\}$. We want to prove $A I = A$ for $A \geq O$.

For $0 < a \in A$, since $A$ is a cut, then we can find $a < b \in A$, let $c = a / b < 1$, so $c \in I$. then $bc = b (a/b) = a$, so $a \in AI$. We have $A \subseteq AI$.

For $0 \leq c \in AI$, we can find $a \in A, b \in B$ such that $c = ab$. Since $b < 1$, then $c < a$, then $c \in A$, That is $AI \subseteq A$.

$\square$

(c) Show the distributive property (f5) holds for non-negative cuts.

Proof: We want to show $A(B+C) = AB + AC$ for $A, B, C \geq O$.

First of all, if $q < 0$, then $q \in A(B+C)$. Also $q \in AB, 0 \in AC$, so $q \in AB + AC$.

Secondly, $0 \in A, B, C$, so $0 \in A(B+C)$, and $0 \in AB+AC$.

If $0 < q \in AB+AC$, assume $q = r+s$. If $r > 0, s \leq 0$ and $r = ab$. Let $c = s/a$, since $c \leq 0$ then $c \in C$.

$$a (b + c) = ab + a (s/a) = r + s = q$$

Similarly, we can prove if $r \leq 0, s > 0$.

Now assume $r > 0, s > 0$. $r = a_1 b, s = a_2 c$. If $a1 \geq a_2$, then $s = a_1 (a_2 / a_1) c$. $(a_2 / a_1) c \leq c$, so $(a_2 / a_1) c \in C$.

$a_1 (b + (a_2 / a_1)c) = a_1b + a_2c = q$, so $q \in A(B+C)$.

Then we have $A(B+C) \supseteq AB + AC$.

The other direction, assume $a(b+c) \in A(B+C), a \geq 0, (b+c)\geq 0$.

$$a(b+c) = ab + ac$$

If $b \geq 0$, then $ab \in AB$. If $b < 0$, $ab \leq 0$, $ab \in AB$. Same thing for $ac$.

Then $a(b+c) \in AB+AC$, i.e. $A(B+C) \subseteq AB + AC$.

So $A(B+C) = AB + AC$.

$\square$

Products involving at least one negative factor can be defined in terms of the product of two positive cuts by observing that $−A ≥ 0$ whenever $A ≤ O$. (Given $A ≤ O$, property (o4) implies $A+(−A) ≤ O +(−A)$, which yields $O ≤ −A.$)

$$AB = \begin{cases} \text{ as given } &\text{if } A ≥ O \text{ and } B ≥ O\\ -[A(-B)] &\text{if } A ≥ O \text{ and } B < O\\ -[(-A)B] &\text{if } A < O \text{ and } B ≥ O\\ (-A)(-B) &\text{if } A < O \text{ and } B < O\\ \end{cases}$$

Least Upper Bounds

Definition 8.6.6.

A set $\mathcal{A} ⊆ R$ is bounded above if there exists a $B ∈ R$ such that $A ≤ B$ for all $A ∈ \mathcal{A}$. The number $B$ is called an upper bound for $\mathcal{A}$.

A real number $S ∈ R$ is the least upper bound for a set $\mathcal{A} ⊆ R$ if it meets the following two criteria

(i) $S$ is an upper bound for $\mathcal{A}$ and

(ii) if $B$ is any upper bound for $\mathcal{A}$, then $S ≤ B$.

Exercise 8.6.8.

Let $\mathcal{A} ⊆ R$ be nonempty and bounded above, and let $S$ be the union of all $A ∈ \mathcal{A}$.

(a) First, prove that $S ∈ \mathbf{R}$ by showing that it is a cut.

Proof:

(c1) $\mathcal{A}$ is not empty and $A \in \mathcal{A}$. $A$ is not empty, and $A \subseteq S$. So $S$ is not empty.

$\mathcal{A}$ is bounded above, so we can find $B$ such that $A ≤ B$ for all $A ∈ \mathcal{A}$.

$B$ is a cut so we can find $c \not \in B$. If $c \in A$ for some $A$, then $c \in A \subseteq B$. We have a contradiction. So $c \not \in A$ for all $A ∈ \mathcal{A}$. Then $c \not \in S$, so $S \neq \mathbf{Q}$.

(c2) if $r \in S$ and $s < r$. Then we can find $A$ such that $r \in A$. Since $s < r$, then $s \in A$. So $s \in S$.

(c3) Similarly, assume $a \in S$, then $a \in A$ for some $A$. then we can find $b \in A$, such that $a < b$. Since $b \in A$, then $S$ does not have a maximum.

$\square$

(b) Now, show that $S$ is the least upper bound for $\mathcal{A}$.

Proof: Given $A \in \mathcal{A}$, $A \subseteq S$, i.e. $A \leq S$. So $S$ is an upper bound of $\mathcal{A}$.

Let $B$ be an upper bound. Given $a \in S$, we can find $A$ such that $a \in A$. Then $a \in A \subseteq B$, so $S \subseteq B$.

So $S$ is the least upper bound for $\mathcal{A}$.

$\square$

Exercise 8.6.9.

Consider the collection of so-called “rational” cuts of the form

$$C_r = \{t \in \mathbf{Q} : t < r\}$$

where $r \in \mathbf{Q}$.

(a) Show that $C_{r} + C_{s} = C_{r+s}$ for all $r,s ∈ \mathbf{Q}$. Verify $C_{r} C_{s} = C_{rs}$ for the case when $r,s ≥ 0$.

Proof: Given $a \in C_r, b \in C_s$, we have $a < r, b < s$. Then $a + b < r + s$. So $C_{r} + C_{s} \leq C_{r+s}$.

Given $c \in C_{r+s}$, then $c < r + s$. Let $e = \frac{r+s-c}{2} > 0$ and $a = r-e, b = s - e$.

Then $a+b = (r-e) + (s - e) = (r+s) - 2e = c$. So $C_{r} + C_{s} \geq C_{r+s}$.

In summary, we have $C_{r} + C_{s} = C_{r+s}$.

If $r = 0$, $C_r = O$. $rs = 0$, then $C_{rs} = O$. We just need to prove $O C_s = O$.

Note $O C_s = \{q ∈ Q : q < 0\} = O$.

Same thing for $s = 0$.

Next we only need to prove $r > 0, s > 0$.

Given $0 < c = ab < rs \in C_{rs}$.

On the other hand, give $0 < c < rs$. Let $d = \sqrt[]{\frac{c}{rs}} < 1$. Let $a = dr < r, b = ds < s$.

$$ab = d^2 rs = c$$

So $c \in C_r C_s$.

We have $C_{r} C_{s} = C_{rs}$

$\square$

(b) Show that $C_r ≤ C_s$ if and only if $r ≤ s$ in $\mathbf{Q}$.

Proof:

If $r \leq s$, $a \in C_r$, so $a < r \leq s$. $a \in C_s$.

if $C_r \leq C_s$ and $r > s$. Consider $r > \frac{r+s}{2} > s$, then $\frac{r+s}{2} \not\in C_s$, but $\frac{r+s}{2} \in C_r$. We got a contradiction.

So $r \leq s$.

$\square$

Cantor’s Approach

Cantor’s idea was essentially to define a real number to be the entire Cauchy sequence. The first problem one encounters with this approach is the realization that two different Cauchy sequences can converge to the same real number. For this reason, the elements in R are more appropriately defined as equivalence classes of Cauchy sequences where two sequences $(x_n)$ and $(y_n)$ are in the same equivalence class if and only if $(x_n−y_n) → 0$.

$\square$