7.2 Order by Inclusion, and Least Upper Bounds by Unions

This section belongs to the optional Chapter 7; nothing outside the chapter depends on it. Section 7.1 defined a cut as a set of rationals that is non-empty and not all of $\mathbb{Q}$ , closed downward, and without a largest element (Definition 7.1.1), and it called the set of all cuts $\mathbb{R}_{\mathrm D}$ . Before cuts can be added or multiplied, they can already be compared, and the comparison costs nothing: one cut is below another when it is contained in it. This section shows that this order is total, and then proves the property that the Cauchy road of Chapter 5 reached only at its end. Every non-empty set of cuts that is bounded above has a least upper bound, and that least upper bound is simply the union of the set.

7.2.1. Comparing cuts

For two rationals $p$ and $q$ , “ $p$ is at most $q$ ” says the same as “every rational below $p$ is below $q$ ”. In the language of Section 7.1, $p \le q$ holds exactly when $D_p \subseteq D_q$ : if $p \le q$ and $r < p$ , then $r < q$ ; and if $q < p$ , then $q \in D_p \setminus D_q$ . So on rational cuts, inclusion is the order of $\mathbb{Q}$ in disguise. We take it as the order of all cuts.

One cut is below another when every rational in the first is also in the second.

Definition 7.2.1 (Order of Cuts)

For cuts $\alpha$ and $\beta$ , we write $\alpha \le \beta$ if $\alpha \subseteq \beta$ , and $\alpha < \beta$ if $\alpha \subsetneq \beta$ , that is, if $\alpha \subseteq \beta$ and $\alpha \ne \beta$ . As usual, $\beta \ge \alpha$ means $\alpha \le \beta$ , and $\beta > \alpha$ means $\alpha < \beta$ .

The relation $\le$ is a partial order on $\mathbb{R}_{\mathrm D}$ (Sets, Relations, and Cardinality, Definition 2.6.1): it is reflexive, since $\alpha \subseteq \alpha$ ; antisymmetric, since $\alpha \subseteq \beta$ and $\beta \subseteq \alpha$ give $\alpha = \beta$ (Sets, Relations, and Cardinality, Proposition 1.1.1); and transitive (Sets, Relations, and Cardinality, Proposition 1.1.2). Its strict part, $\alpha \le \beta$ and $\alpha \ne \beta$ , is exactly $<$ . These are the facts that make inclusion a partial order on all of $\mathcal{P}\left( \mathbb{Q} \right)$ (Sets, Relations, and Cardinality, Example (Inclusion is a partial order, rarely total)), restricted to the cuts.

Two translations. First, the order of $\mathbb{Q}$ is recovered on rational cuts: for $p, q \in \mathbb{Q}$ , $p < q \iff D_p < D_q , \qquad p = q \iff D_p = D_q .$ Indeed, Proposition 7.1.2 (a) with $\alpha = D_q$ says $p \in D_q \iff D_p \subsetneq D_q$ , and $p \in D_q$ means $p < q$ . For the second equivalence, if $p \ne q$ , then $p < q$ or $q < p$ , and either way $D_p \ne D_q$ by the first. Second, Proposition 7.1.2 now reads, for a cut $\alpha$ and $q \in \mathbb{Q}$ , $q \in \alpha \iff D_q < \alpha , \qquad q \notin \alpha \iff \alpha \le D_q .$ So “the rational $q$ lies in the cut $\alpha$ ” and “the rational cut of $q$ is strictly below $\alpha$ ” are the same statement. This is the precise sense in which a cut is the set of rationals below it.

Quick check. Show that $D_1 < \sigma < D_{3/2}$ , where $\sigma$ is the cut of Example (The cut of the gap).

Solution. By the second translation, $D_1 < \sigma$ because $1 \in \sigma$ ( $1^2 = 1 < 2$ ), and $\sigma \le D_{3/2}$ because $3/2 \notin \sigma$ ( $3/2 > 0$ and $(3/2)^2 = 9/4 > 2$ ). The inclusion $\sigma \subseteq D_{3/2}$ is proper: $29/20$ lies in $D_{3/2}$ , since $29 \cdot 2 = 58 < 60 = 3 \cdot 20$ , but not in $\sigma$ , since $29/20 > 0$ and $(29/20)^2 = 841/400 > 2$ (as $841 > 800$ ). So $\sigma < D_{3/2}$ .

Inclusion is rarely a total order: in $\mathcal{P}\left( \mathbb{Q} \right)$ , neither of $\{0\}$ and $\{1\}$ contains the other. Among cuts it is total, and the reason is separation.

Theorem 7.2.1 (Cuts Are Totally Ordered)

For all cuts $\alpha$ and $\beta$ , $\alpha \le \beta$ or $\beta \le \alpha$ . Hence exactly one of $\alpha < \beta$ , $\alpha = \beta$ , $\beta < \alpha$ holds.

Idea. If $\alpha$ is not inside $\beta$ , then $\alpha$ has a point $p$ outside $\beta$ . Everything in $\beta$ lies below every outside point of $\beta$ , so below $p$ ; and $\alpha$ , being closed downward, contains everything below its point $p$ . So $\alpha$ contains all of $\beta$ .

Proof. Let $\alpha, \beta$ be cuts. If $\alpha \subseteq \beta$ , then $\alpha \le \beta$ and we are done; so suppose $\alpha \not\subseteq \beta$ . Then some $p \in \alpha$ has $p \notin \beta$ . Let $q \in \beta$ be arbitrary. Since $q \in \beta$ and $p \notin \beta$ , Lemma 7.1.1 gives $q < p$ . Since $p \in \alpha$ and $q < p$ , (C2) for $\alpha$ gives $q \in \alpha$ . As $q$ was arbitrary, $\beta \subseteq \alpha$ , that is, $\beta \le \alpha$ .

For the second statement: if $\alpha \le \beta$ , then $\alpha = \beta$ or $\alpha < \beta$ ; otherwise $\beta \le \alpha$ and $\beta \ne \alpha$ , that is, $\beta < \alpha$ . So at least one of the three holds. No two hold together: $\alpha < \beta$ and $\beta < \alpha$ would give $\alpha = \beta$ by antisymmetry, against $\alpha \ne \beta$ ; and $\alpha < \beta$ excludes $\alpha = \beta$ by definition, as $\beta < \alpha$ does.

The proof used (C2), directly and through Lemma 7.1.1, whose proof uses only (C2) and trichotomy in $\mathbb{Q}$ ; it never used (C1) or (C3). So any two subsets of $\mathbb{Q}$ that are closed downward are comparable by inclusion. The pair $\{0\}$ , $\{1\}$ fails (C2), and that is why it could be incomparable.

With Theorem 7.2.1, $(\mathbb{R}_{\mathrm D}, \le)$ is a totally ordered set, and the vocabulary of Sets, Relations, and Cardinality, Section 2.6 applies to it: a set $A \subseteq \mathbb{R}_{\mathrm D}$ is bounded above if some cut $\beta$ has $\alpha \le \beta$ for every $\alpha \in A$ (Sets, Relations, and Cardinality, Definition 2.6.2), and a cut $\gamma$ is its supremum if it is an upper bound of $A$ , clause (S1), and $\gamma \le \delta$ for every upper bound $\delta$ of $A$ , clause (S2) (Sets, Relations, and Cardinality, Definition 2.6.5). A supremum is unique when it exists (Sets, Relations, and Cardinality, Proposition 2.6.1, applied to the set of upper bounds).

7.2.2. Least upper bounds are unions

In $\mathbb{Q}$ , the set $\{ x \in \mathbb{Q} : x^2 < 2 \}$ is non-empty and bounded above, and has no supremum (Theorem 2.6.2). The cuts were built so that no such gap remains, and here is the theorem that says so.

Theorem 7.2.2 (Least Upper Bounds of Cuts)

Let $A \subseteq \mathbb{R}_{\mathrm D}$ be non-empty and bounded above: some cut $\beta$ has $\alpha \le \beta$ for every $\alpha \in A$ . Then $\gamma \mathrel{:=} \bigcup A = \{ p \in \mathbb{Q} : p \in \alpha \text{ for some } \alpha \in A \}$ (Sets, Relations, and Cardinality, Definition 1.2.4, the family indexed by $A$ itself) is a cut, and $\gamma$ is the supremum of $A$ in $(\mathbb{R}_{\mathrm D}, \le)$ .

Try it first (ten minutes): which cut would you propose as the supremum of a set of cuts? Check your proposal against (C1)–(C3), and then against (S1) and (S2).

Idea. The word “bounds” invites a first guess: the intersection $\bigcap A$ , the rationals common to all members. It sits on the wrong side. The intersection lies inside every member, so it is a candidate for a lower bound, the infimum’s job, and it can even fail to be a cut (try it in Exercise C1). An upper bound must contain every member, and the smallest set that does is the union. In $\mathcal{P}\left( \mathbb{Q} \right)$ the union is the supremum: it contains every member, and any set that contains every member contains the union ((S1) and (S2) in the proof below check this for cuts). So everything comes down to one question: is the union a cut? Conditions (C2) and (C3) pass from the members to the union one element at a time, and (C1) needs both hypotheses, one for each half. Before reading on: which of the three conditions will use “bounded above”?

Proof. Let $\beta$ be an upper bound of $A$ . The set $\gamma$ is a subset of $\mathbb{Q}$ , since every member of $A$ is.

(C1). Since $A$ is non-empty, fix $\alpha_0 \in A$ ; since $\alpha_0 \ne \emptyset$ by (C1) for $\alpha_0$ , fix $p_0 \in \alpha_0$ . Then $p_0 \in \gamma$ , so $\gamma \ne \emptyset$ . Next, $\gamma \subseteq \beta$ : if $p \in \gamma$ , then $p \in \alpha$ for some $\alpha \in A$ $[\mathrm{\exists E}]$ , and $\alpha \subseteq \beta$ because $\beta$ is an upper bound, so $p \in \beta$ . By (C1) for $\beta$ , some $b \in \mathbb{Q}$ has $b \notin \beta$ ; then $b \notin \gamma$ , so $\gamma \ne \mathbb{Q}$ .

(C2). Let $p \in \gamma$ and $q \in \mathbb{Q}$ with $q < p$ . Then $p \in \alpha$ for some $\alpha \in A$ $[\mathrm{\exists E}]$ . By (C2) for $\alpha$ , $q \in \alpha$ , so $q \in \gamma$ .

(C3). Let $p \in \gamma$ , say $p \in \alpha$ with $\alpha \in A$ $[\mathrm{\exists E}]$ . By (C3) for $\alpha$ , some $p' \in \alpha$ has $p' > p$ , and $p' \in \gamma$ .

So $\gamma$ is a cut. (S1). For each $\alpha \in A$ , every element of $\alpha$ lies in $\gamma$ , so $\alpha \subseteq \gamma$ , that is, $\alpha \le \gamma$ . (S2). Let $\delta$ be an upper bound of $A$ . If $p \in \gamma$ , then $p \in \alpha$ for some $\alpha \in A$ $[\mathrm{\exists E}]$ , and $\alpha \subseteq \delta$ , so $p \in \delta$ . Thus $\gamma \subseteq \delta$ , that is, $\gamma \le \delta$ . Hence $\gamma$ is the supremum of $A$ .

The answer to the prompt: “bounded above” is used once, in the second half of (C1), to show $\gamma \ne \mathbb{Q}$ . “Non-empty” is used once too, in the first half of (C1). Conditions (C2) and (C3) of $\gamma$ , and the clauses (S1) and (S2), hold for every set of cuts; it is only being a cut at all that needs the hypotheses.

Compare the Cauchy road. There, completeness took two sections: Section 5.5 proved that every Cauchy sequence of real numbers converges, by building rational approximants, and Section 5.6 bisected intervals, with one line that needed the Archimedean property, to reach least upper bounds. Here it took one union and five short checks, (C1)–(C3) and (S1)–(S2). The proof above uses no arithmetic of $\mathbb{Q}$ at all, only its order, through (C2) and (C3) of the members; in particular it does not use the Archimedean property. The price is paid elsewhere: cuts have no sum or product yet, and Sections 7.3 and 7.4 build them, multiplication with some effort.

Warning. Both hypotheses of Theorem 7.2.2 are needed for the union to be a cut. Drop “bounded above”: the rational cuts $D_n$ , $n \in \mathbb{N}$ , have union $\mathbb{Q}$ , since every rational $r$ lies below some $n \in \mathbb{N}$ (Theorem 2.5.3) and so in $D_n$ ; and $\mathbb{Q}$ fails (C1). Drop “non-empty”: $\bigcup \emptyset = \emptyset$ , which fails (C1) too.

Second readingThe empty set and unbounded sets have no supremum among cuts

The warning shows that the proof breaks without each hypothesis. In fact the conclusion fails too: without either hypothesis, there is no supremum at all.

The empty set. Every cut is an upper bound of $\emptyset$ , vacuously, so a supremum of $\emptyset$ would be a least cut. There is none: for a cut $\alpha$ , pick $a \in \alpha$ (C1); then $D_a < \alpha$ by Proposition 7.1.2 (a), and $D_a$ is a cut, so $\alpha$ is not least.

An unbounded set. A set with no upper bound has no supremum, since a supremum is an upper bound by (S1). For example $\{ D_n : n \in \mathbb{N} \}$ has none: if $\beta$ bounded it, then $\mathbb{Q} = \bigcup_{n \in \mathbb{N}} D_n \subseteq \beta$ , against (C1) for $\beta$ .

Quick check. Find $\sup \{ D_{1 - 1/n} : n \in \mathbb{Z}_{>0} \}$ in $(\mathbb{R}_{\mathrm D}, \le)$ . Is it an element of the set?

Solution. The set is non-empty and bounded above by $D_1$ , since $1/n > 0$ (Proposition 2.5.2 (a)), so $1 - 1/n < 1$ and $D_{1 - 1/n} \subseteq D_1$ . By Theorem 7.2.2 its supremum is the union $U \mathrel{:=} \bigcup_{n \ge 1} D_{1 - 1/n}$ . We show $U = D_1$ . $(\subseteq)$ : if $r < 1 - 1/n$ for some $n$ , then $r < 1$ . $(\supseteq)$ : let $r < 1$ . Then $1 - r > 0$ , and Corollary 2.5.4 gives $n \in \mathbb{Z}_{>0}$ with $1/n < 1 - r$ , that is, $r < 1 - 1/n$ , so $r \in U$ . Hence the supremum is $D_1$ . It is not in the set: $D_{1 - 1/n} = D_1$ would force $1 - 1/n = 1$ by the first translation, and $1/n \ne 0$ .

So $(\mathbb{R}_{\mathrm D}, \le)$ is a totally ordered set in which every non-empty subset that is bounded above has a supremum. Once Sections 7.3 and 7.4 have made $\mathbb{R}_{\mathrm D}$ an ordered field with this order, Section 7.5 reads Theorem 7.2.2 as the statement that it is a complete ordered field (Definition 5.6.1).

7.2.3. Exercises

A. Check your understanding

Exercise (A1)

These questions are about Theorem 7.2.2 and its proof.

(a) Let $A \mathrel{:=} \{ D_q : q \in \sigma \}$ , with $\sigma$ the cut of Example (The cut of the gap). Check that $A$ satisfies the hypotheses, and find the cut $\gamma$ of the proof, arguing directly from (C2) and (C3) of $\sigma$ .
(b) State the idea of the proof in two sentences.
(c) Which line of the proof fails if $A = \emptyset$ , and what is $\gamma$ then?
(d) In the check of (C3) for $\gamma$ , which cut’s condition (C3) is used?

Solution.

(a) $A$ is non-empty, since $0 \in \sigma$ gives $D_0 \in A$ . It is bounded above by $\sigma$ : for $q \in \sigma$ , $D_q < \sigma$ by Proposition 7.1.2 (a). The proof’s cut is $\gamma = \bigcup_{q \in \sigma} D_q$ , and $\gamma = \sigma$ . $(\subseteq)$ : each $D_q$ with $q \in \sigma$ is contained in $\sigma$ , by (C2) of $\sigma$ . $(\supseteq)$ : let $q \in \sigma$ ; by (C3) of $\sigma$ there is $q' \in \sigma$ with $q' > q$ , so $q \in D_{q'} \subseteq \gamma$ . So $\sup A = \sigma$ : the cut of the gap is the supremum of the rational cuts below it.
(b) The union of the cuts contains each of them, and lies inside every upper bound, so it is the least upper bound once it is known to be a cut. It is one because (C2) and (C3) pass from the members to the union element by element, while (C1) comes from $A \ne \emptyset$ (some element) and from an upper bound $\beta \ne \mathbb{Q}$ (some non-element).
(c) The first line of (C1): with $A = \emptyset$ there is no $\alpha_0 \in A$ to fix. Then $\gamma = \bigcup \emptyset = \emptyset$ , which is not a cut.
(d) Condition (C3) of the member $\alpha \in A$ that contains the given $p \in \gamma$ . Different points of $\gamma$ may use different members.

B. Practice

Exercise (B1)

Let $q, r \in \mathbb{Q}$ . Prove that $\sup \{ D_q, D_r \} = D_{\max(q, r)}$ in $(\mathbb{R}_{\mathrm D}, \le)$ .

Solution. Let $m \mathrel{:=} \max(q, r)$ . Since $q \le m$ and $r \le m$ , $D_q \subseteq D_m$ and $D_r \subseteq D_m$ (if $s < q \le m$ , then $s < m$ ); so $\{ D_q, D_r \}$ is non-empty and bounded above by $D_m$ . By Theorem 7.2.2 its supremum is $D_q \cup D_r$ . This union contains $D_m$ , because $D_m$ is one of $D_q$ , $D_r$ ; and it is contained in $D_m$ , by the two inclusions above. Hence $\sup \{ D_q, D_r \} = D_q \cup D_r = D_m$ .

Exercise (B2: Put the proof in order)

Here are lines of a proof that for cuts $\alpha$ and $\beta$ , $\alpha \le \beta$ or $\beta \le \alpha$ , shuffled, together with two lines that do not belong. Without looking back, write the lines of a correct proof in a correct order, and say what is wrong with each line you leave out.

(i) Let $q \in \beta$ be arbitrary.
(ii) Since $q < p$ and $p \in \alpha$ , $q \in \beta$ .
(iii) As $q$ was arbitrary, $\beta \subseteq \alpha$ .
(iv) Let $\alpha$ , $\beta$ be cuts with $\alpha \not\subseteq \beta$ (if $\alpha \subseteq \beta$ , there is nothing to prove).
(v) Since $p \in \alpha$ and $q < p$ , $q \in \alpha$ , because $\alpha$ is closed downward.
(vi) Since $q \in \beta$ and $p \notin \beta$ , $p < q$ .
(vii) Then some $p \in \alpha$ has $p \notin \beta$ .
(viii) Since $q \in \beta$ and $p \notin \beta$ , $q < p$ , by separation.

Solution. An admissible order is $\text{(iv)}, \ \text{(vii)}, \ \text{(i)}, \ \text{(viii)}, \ \text{(v)}, \ \text{(iii)} .$ Line (i) may also come before (vii), since it only introduces a name for an arbitrary element of $\beta$ , and (vii) does not mention $q$ . Otherwise the order is forced: (vii) unwinds the assumption of (iv); (viii) needs $p$ from (vii) and $q$ from (i); (v) needs $q < p$ from (viii); and (iii) closes the argument about the arbitrary $q$ .

Line (vi) reads separation backwards. Lemma 7.1.1 puts a point inside a cut below a point outside it. Here $q$ is inside $\beta$ and $p$ is outside, so separation gives $q < p$ , as in (viii); line (vi) asserts the opposite, and the two together contradict (O1).

Line (ii) applies closure to the wrong cut. Closure downward of $\alpha$ turns “ $p \in \alpha$ and $q < p$ ” into $q \in \alpha$ , not into $q \in \beta$ ; the fact that $p \in \alpha$ says nothing about $\beta$ . (Its conclusion $q \in \beta$ is true, but only because it was assumed in (i).)

C. Going deeper

Exercise (C1: Infima)

Let $A \subseteq \mathbb{R}_{\mathrm D}$ be non-empty and bounded below.

(a) Show that $\bigcap A$ need not be a cut, by computing $\bigcap A_0$ for $A_0 \mathrel{:=} \{ D_{1/n} : n \in \mathbb{Z}_{>0} \}$ .
(b) Prove that $A$ nevertheless has an infimum in $(\mathbb{R}_{\mathrm D}, \le)$ : it is the supremum of the set of lower bounds of $A$ .
(c) Find $\inf A_0$ .

Solution (Hint 1). For (b), the set $L$ of lower bounds of $A$ is non-empty by hypothesis. Find an upper bound for $L$ among the elements of $A$ .

Solution (Hint 2). Let $\lambda_0 \mathrel{:=} \sup L$ , which exists by Theorem 7.2.2; the claim is that $\lambda_0 = \inf A$ .

Solution.

(a) Here $\bigcap A_0 = \{ r \in \mathbb{Q} : r < 1/n \text{ for every } n \in \mathbb{Z}_{>0} \}$ , the intersection taken in $\mathbb{Q}$ . We claim it is $\{ r \in \mathbb{Q} : r \le 0 \}$ . If $r \le 0$ , then $r \le 0 < 1/n$ for every $n$ (Proposition 2.5.2 (a)). If $r > 0$ , Corollary 2.5.4 gives $n$ with $1/n < r$ , so $r \notin D_{1/n}$ and $r \notin \bigcap A_0$ . The set $\{ r : r \le 0 \}$ has the largest element $0$ , so it fails (C3) and is not a cut. (The set $A_0$ is non-empty and bounded below, by $D_0$ , for instance.)
(b) Let $L \mathrel{:=} \{ \lambda \in \mathbb{R}_{\mathrm D} : \lambda \le \alpha \text{ for every } \alpha \in A \}$ , the set of lower bounds of $A$ . It is non-empty, since $A$ is bounded below. It is bounded above: fix $\alpha_0 \in A$ ( $A \ne \emptyset$ ); every $\lambda \in L$ has $\lambda \le \alpha_0$ . By Theorem 7.2.2, $L$ has a supremum $\lambda_0$ .

$\lambda_0$ is a lower bound of $A$ . Let $\alpha \in A$ . Every $\lambda \in L$ has $\lambda \le \alpha$ , so $\alpha$ is an upper bound of $L$ , and (S2) for $\lambda_0 = \sup L$ gives $\lambda_0 \le \alpha$ .

$\lambda_0$ is the greatest lower bound. We just showed $\lambda_0 \in L$ . If $\lambda$ is any lower bound of $A$ , then $\lambda \in L$ , so $\lambda \le \lambda_0$ by (S1) for $\lambda_0$ . Hence $\lambda_0 = \inf A$ .
(c) $\inf A_0 = D_0$ . It is a lower bound: $D_0 \subseteq D_{1/n}$ since $0 < 1/n$ . Let $\lambda$ be any lower bound. Then $\lambda \subseteq \bigcap A_0 = \{ r : r \le 0 \}$ by (a). And $0 \notin \lambda$ : otherwise (C3) for $\lambda$ gives $p' \in \lambda$ with $p' > 0$ , but $\lambda$ contains no positive rational. So every element of $\lambda$ is negative, $\lambda \subseteq D_0$ , and $\lambda \le D_0$ . So the infimum is the intersection with its largest element removed.

Marking scheme. (10 points) - 2: (a) computes $\bigcap A_0 = \{ r : r \le 0 \}$ , using the Archimedean property for the positive rationals, and names (C3) as the failing condition. - 2: (b) shows that the set of lower bounds is non-empty and bounded above by a member of $A$ . - 2: (b) shows that its supremum is a lower bound of $A$ , through (S2). - 2: (b) shows that it is the greatest lower bound, through (S1). - 2: (c) identifies $D_0$ , with both inequalities. Fatal errors (0 for the step): asserting that $\bigcap A$ is the infimum without checking (C3); using a supremum of $L$ without checking that $L$ is non-empty and bounded above.

Exercise (C2: Find the error)

Here is a proof. Its conclusion is the first half of Theorem 7.2.2.

Claim. Let $A \subseteq \mathbb{R}_{\mathrm D}$ be non-empty and bounded above. Then $\gamma \mathrel{:=} \bigcup A$ is a cut.

Since $A$ is non-empty, pick $\alpha_0 \in A$ ; since $\alpha_0 \ne \emptyset$ , pick $p_0 \in \alpha_0$ . Then $p_0 \in \gamma$ , so $\gamma \ne \emptyset$ . (2) Each $\alpha \in A$ is a cut, so $\alpha \ne \mathbb{Q}$ . Hence $\gamma \ne \mathbb{Q}$ . (3) Let $p \in \gamma$ and $q < p$ . Then $p \in \alpha$ for some $\alpha \in A$ , so $q \in \alpha$ by (C2), and $q \in \gamma$ . (4) Let $p \in \gamma$ . Then $p \in \alpha$ for some $\alpha \in A$ ; by (C3) there is $p' \in \alpha$ with $p' > p$ , and $p' \in \gamma$ . (5) So $\gamma$ satisfies (C1)–(C3).

Is the conclusion true? Does the argument prove it? If not, name the line that fails, say what is illegal about it, and give a counterexample to that step.

Solution. The conclusion is true: it is proved in Theorem 7.2.2. The argument does not prove it, because line (2) fails.

What is illegal. Line (2) passes from “for every $\alpha \in A$ there is a rational outside $\alpha$ ” to “there is a rational outside every $\alpha \in A$ ”, which is what $\gamma \ne \mathbb{Q}$ means. The rational outside $\alpha$ depends on $\alpha$ , and the line uses it as if one rational served every member at once. This is the move (N2) of Logic and Proof, Example (What is not allowed): a witness found inside the box of one $\alpha$ is treated as uniform in $\alpha$ . A union of proper subsets of $\mathbb{Q}$ can be all of $\mathbb{Q}$ .

Counterexample to the step. Let $A' \mathrel{:=} \{ D_n : n \in \mathbb{N} \}$ . Each $D_n$ is a cut, so $D_n \ne \mathbb{Q}$ , and the premise of the step holds; but $\bigcup A' = \mathbb{Q}$ , since every rational lies below some natural number (Theorem 2.5.3). So the step leads from a true premise to a false conclusion. (This $A'$ is not bounded above, so it is not a counterexample to the claim, which is true.)

The tell. The hypothesis “bounded above” is never used. A correct proof must use it, since the warning after Theorem 7.2.2 shows that the claim fails without it.

Repair. Let $\beta$ be an upper bound of $A$ . Every $\alpha \in A$ satisfies $\alpha \subseteq \beta$ , so $\gamma \subseteq \beta$ ; and $\beta \ne \mathbb{Q}$ , so some $b \notin \beta$ , hence $b \notin \gamma$ and $\gamma \ne \mathbb{Q}$ .

Exercise (C3: Exit check: least upper bounds of cuts)

Let $A$ be a non-empty set of cuts, bounded above in $(\mathbb{R}_{\mathrm D}, \subseteq)$ . Prove that $\bigcup A$ is a cut and that it is the supremum of $A$ .

Solution. Let $\gamma \mathrel{:=} \bigcup A$ and let $\beta$ be an upper bound of $A$ .

(C1). Pick $\alpha_0 \in A$ and $p_0 \in \alpha_0$ , possible since $A \ne \emptyset$ and $\alpha_0 \ne \emptyset$ ; then $p_0 \in \gamma$ . Every element of $\gamma$ lies in some $\alpha \in A$ , and $\alpha \subseteq \beta$ , so $\gamma \subseteq \beta$ . Pick $b \in \mathbb{Q} \setminus \beta$ (C1 for $\beta$ ); then $b \notin \gamma$ . So $\emptyset \ne \gamma \ne \mathbb{Q}$ .

(C2). If $q < p$ with $p \in \gamma$ , then $p \in \alpha$ for some $\alpha \in A$ , so $q \in \alpha \subseteq \gamma$ .

(C3). If $p \in \gamma$ , then $p \in \alpha$ for some $\alpha \in A$ , and (C3) for $\alpha$ gives $p' \in \alpha \subseteq \gamma$ with $p' > p$ .

Upper bound. Each $\alpha \in A$ satisfies $\alpha \subseteq \gamma$ .

Least. If $\delta$ is a cut with $\alpha \subseteq \delta$ for every $\alpha \in A$ , then every $p \in \gamma$ lies in some $\alpha \in A$ , hence in $\delta$ ; so $\gamma \subseteq \delta$ .

So $\gamma$ is a cut, an upper bound of $A$ , and below every upper bound: $\gamma = \sup A$ .

Marking scheme. (10 points) - 2: $\gamma \ne \emptyset$ from $A \ne \emptyset$ , and $\gamma \ne \mathbb{Q}$ from the upper bound $\beta \ne \mathbb{Q}$ . - 2: $\gamma$ closed downward. - 2: $\gamma$ has no largest element. - 2: $\gamma$ is an upper bound of $A$ . - 2: $\gamma$ is below every upper bound of $A$ . Fatal errors (0 for the step): “ $\gamma \ne \mathbb{Q}$ because each $\alpha \ne \mathbb{Q}$ ” (the error of Exercise C2); comparing cuts with “ $\le$ ” as if they were rationals, instead of by inclusion.