3.2 The Rationals as an Ordered Field; the Archimedean Property

Section 3.1 made $\mathbb{Q}$ a field (Theorem 3.1.3). It did not give $\mathbb{Q}$ an order, and the school number line cannot supply one. We order $\mathbb{Q}$ the way Section 2.4 ordered $\mathbb{Z}$ : name the positive elements, check (P1) and (P2) of Proposition 2.4.1, and read off every rule for inequalities. Then we prove, from the construction and with no supremum anywhere, that every rational lies below a natural number; Chapters 4 and 5 use its form $1/n < \varepsilon$ at every turn. Finally every rational gets an integer part.

3.2.1. Which fractions are positive

Throughout, a rational is written as in Section 3.1. By Proposition 3.1.4 (b), every $x \in \mathbb{Q}$ is $p/q$ for some $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ , where $p/q$ is the class $[(p, q)]$ , and $p/q = r/s$ if and only if $ps = rq$ . The integers sit inside $\mathbb{Q}$ as $m = m/1$ , and the natural numbers inside the integers.

The order of $\mathbb{Z}$ came from its positive set $P_{\mathbb{Z}}$ (Definition 2.4.2), and Proposition 2.4.1 turned closure under $+$ and $\cdot$ , together with a trichotomy, into all of (O1)–(O4). We do the same for $\mathbb{Q}$ , so the whole question is: which fractions should count as positive? A first guess from school is “numerator and denominator have the same sign”. But in $\mathbb{Q}$ the denominator is always positive. That was the decision recorded with Definition 3.1.1, and here it pays: the sign of a fraction is the sign of its numerator.

A fraction with a positive denominator is positive exactly when its numerator is.

Definition 3.2.1 (The Order on

\mathbb{Q}

)

Let $P_{\mathbb{Q}} \mathrel{:=} \bigl\{ [(p, q)] : (p, q) \in \mathbb{Z} \times \mathbb{Z}_{>0} \text{ and } p > 0 \bigr\} .$ For $x, y \in \mathbb{Q}$ , we write $x < y$ if $y - x \in P_{\mathbb{Q}}$ . As in Definition 2.4.1, $x > y$ means $y < x$ , and $x \le y$ means $x < y$ or $x = y$ .

In words: a rational is in $P_{\mathbb{Q}}$ if it has a representative $(p, q)$ with $p > 0$ , the inequality being the order of $\mathbb{Z}$ ; and $x < y$ means that the difference $y - x$ , computed in the field $\mathbb{Q}$ , lies in $P_{\mathbb{Q}}$ .

Well-definedness. The definition says “has a representative with $p > 0$ ”. To use it we want more: that every representative of a class in $P_{\mathbb{Q}}$ has a positive numerator, so that the test can be run on whichever representative is at hand. This is the situation of Theorem 2.2.1 (c), with $X = \mathbb{Z} \times \mathbb{Z}_{>0}$ and $S = \{ (p, q) \in X : p > 0 \}$ . Its hypothesis asks: if $(p, q) \sim (p', q')$ and $p > 0$ , is $p' > 0$ ? It is, and the reason is the sign of the denominators.

Suppose $pq' = p'q$ with $q, q' \in \mathbb{Z}_{>0}$ and $p > 0$ . Since $q, q' > 0$ (Theorem 2.4.2 (b)), (O4) gives $pq' > 0$ , so $p'q > 0$ . If $p' = 0$ , then $p'q = 0$ (Proposition 2.3.2 (b)); if $p' < 0$ , then $p'q < 0 \cdot q = 0$ by Proposition 2.4.3 (c), since $q > 0$ . Both contradict $p'q > 0$ by trichotomy, so $p' > 0$ . Now Theorem 2.2.1 (c) gives, for every $(p, q) \in \mathbb{Z} \times \mathbb{Z}_{>0}$ ,

[(p, q)] \in P_{\mathbb{Q}} \iff p > 0 .

(3.2.1)

Examples. The class $3/4 = 6/8$ lies in $P_{\mathbb{Q}}$ , with both numerators positive, as Eq. 3.2.1 says it must; $-6/8$ does not. Zero does not: $0 = 0/7$ , and $0 > 0$ fails. That matters for (P2), which asks for exactly one of $x \in P_{\mathbb{Q}}$ , $x = 0$ , $-x \in P_{\mathbb{Q}}$ .

Non-example by minimal change. Allow negative denominators: let $Y \mathrel{:=} \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$ with the same cross-multiplication, written $\approx$ . It is still an equivalence relation, since the proof of Proposition 3.1.1 used only $s \ne 0$ . Now $(1, 1) \approx (-1, -1)$ , and the test "the numerator is positive" passes on one representative and fails on the other: the hypothesis of Theorem 2.2.1 (c) fails, at the step " $q > 0$ " of the check above. The comparison of two fractions breaks the same way. For $(0, 1)$ and $(1, 1)$ , the test " $ps < rq$ " asks whether $0 < 1$ , which is true; for $(0, 1)$ and $(-1, -1)$ it asks whether $0 < -1$ , which is false, because multiplying by a negative denominator reverses an inequality (Proposition 2.4.3 (d)).

Warning. Comparing numerators alone is not comparing fractions. The rationals $1/2$ and $2/5$ have $1 < 2$ , yet $1/2 > 2/5$ , since $1/2 - 2/5 = 1/10 \in P_{\mathbb{Q}}$ . Only after bringing both to the same positive denominator do the numerators decide: that is the comparison formula below.

Quick check. Which of $[(-2, 3)]$ , $[(0, 5)]$ , $[(4, 6)]$ lie in $P_{\mathbb{Q}}$ ? Why can one not ask whether $[(2, -3)]$ lies in $P_{\mathbb{Q}}$ ?

Solution. By Eq. 3.2.1, only $[(4, 6)]$ does: its numerator $4$ is positive, while $-2 > 0$ and $0 > 0$ both fail. The symbol $[(2, -3)]$ names no element of $\mathbb{Q}$ : the denominator $-3$ is not in $\mathbb{Z}_{>0}$ , so $(2, -3)$ is not in $\mathbb{Z} \times \mathbb{Z}_{>0}$ and has no class. (The rational one might mean is $-2/3 = [(-2, 3)]$ , which is not in $P_{\mathbb{Q}}$ .)

3.2.2. The rationals form an ordered field

The payoff is that the order of $\mathbb{Q}$ has every property of the order of $\mathbb{Z}$ , together with a formula that compares two fractions with one integer inequality.

Theorem 3.2.1 (The Rationals Form an Ordered Field)

With the order of Definition 3.2.1, $\mathbb{Q}$ is an ordered field (Definition 2.4.1), and $P_{\mathbb{Q}} = \{ x \in \mathbb{Q} : x > 0 \}$ . Moreover:

(a) (The comparison formula.) For $p, r \in \mathbb{Z}$ and $q, s \in \mathbb{Z}_{>0}$ , $\frac{p}{q} < \frac{r}{s} \iff ps < rq ;$ in particular $p/q > 0$ if and only if $p > 0$ .
(b) For $m, n \in \mathbb{Z}$ , $j(m) < j(n)$ if and only if $m < n$ .

Idea. Proposition 2.4.1 reduces everything to (P1) and (P2), and Eq. 3.2.1 turns each into a statement about numerators in $\mathbb{Z}$ : the level below, as in Section 2.3. For $p, r > 0$ , a sum $p/q + r/s$ has numerator $ps + rq$ , positive because $s$ and $q$ are. The comparison formula is the same computation run on a difference. Before reading on: where is $q > 0$ used?

Proof. By Theorem 3.1.3, $\mathbb{Q}$ is a field, in particular a commutative ring. We check (P1) and (P2) of Proposition 2.4.1 for $P = P_{\mathbb{Q}}$ .

(P1) Let $x, y \in P_{\mathbb{Q}}$ , say $x = [(p, q)]$ and $y = [(r, s)]$ with $q, s \in \mathbb{Z}_{>0}$ . By Eq. 3.2.1, $p > 0$ and $r > 0$ ; and $q, s > 0$ by Theorem 2.4.2 (b). By Definition 3.1.2, $x + y = [(ps + rq, \, qs)] , \qquad xy = [(pr, \, qs)] ,$ with $qs \in \mathbb{Z}_{>0}$ . By (O4) in $\mathbb{Z}$ , $ps > 0$ and $rq > 0$ , so $ps + rq > 0 + 0 = 0$ by Proposition 2.4.3 (b); and $pr > 0$ by (O4). By Eq. 3.2.1, $x + y \in P_{\mathbb{Q}}$ and $xy \in P_{\mathbb{Q}}$ .

(P2) Let $x = [(p, q)] \in \mathbb{Q}$ . Then $-x = [(-p, q)]$ (Definition 3.1.2). By Theorem 3.1.3, the zero of $\mathbb{Q}$ is $[(0, 1)]$ , and $x = 0$ if and only if $p = 0$ . By Eq. 3.2.1, $x \in P_{\mathbb{Q}}$ if and only if $p > 0$ , and $-x \in P_{\mathbb{Q}}$ if and only if $-p > 0$ , which by Proposition 2.4.3 (a) means $p < 0$ . By (O1) in $\mathbb{Z}$ , exactly one of $p > 0$ , $p = 0$ , $p < 0$ holds, so exactly one of $x \in P_{\mathbb{Q}}$ , $x = 0$ , $-x \in P_{\mathbb{Q}}$ holds.

By Proposition 2.4.1, the relation $x < y \iff y - x \in P_{\mathbb{Q}}$ , which is the relation of Definition 3.2.1, satisfies (O1)–(O4), and $P_{\mathbb{Q}} = \{ x : x > 0 \}$ . A field that is an ordered commutative ring is an ordered field (Definition 2.4.1).

(a) Let $p, r \in \mathbb{Z}$ and $q, s \in \mathbb{Z}_{>0}$ . By Definition 3.1.2 and Proposition 2.3.2 (c), $\frac{r}{s} - \frac{p}{q} = [(r, s)] + [(-p, q)] = [(rq + (-p)s, \, sq)] = [(rq - ps, \, qs)] .$ So $p/q < r/s$ holds if and only if this class lies in $P_{\mathbb{Q}}$ , that is (by Eq. 3.2.1, since $qs \in \mathbb{Z}_{>0}$ ), if and only if $rq - ps > 0$ , which by Proposition 2.4.3 (a) means $ps < rq$ . For the special case, compare $0 = 0/1$ with $p/q$ : the formula gives $0/1 < p/q$ if and only if $0 \cdot q < p \cdot 1$ , that is, $p > 0$ .
(b) $j(m) = m/1$ and $j(n) = n/1$ (Proposition 3.1.4), so by (a), $j(m) < j(n)$ if and only if $m \cdot 1 < n \cdot 1$ , that is, $m < n$ .

This proves the theorem.

The answer to the prompt: three times. In the well-definedness check, $q$ and $q'$ carry the sign from $p$ to $p'$ ; in (P1), $ps, rq > 0$ ; and in (a), the difference has denominator $qs > 0$ . The non-example above shows the first and the third failing without it.

Since $p/q = r/s$ exactly when $ps = rq$ (Proposition 3.1.4 (b)), the comparison formula has a version with $\le$ : for $q, s \in \mathbb{Z}_{>0}$ ,

\frac{p}{q} \le \frac{r}{s} \iff ps \le rq .

(3.2.2)

By (b) and Theorem 2.4.2 (a), a comparison of two integers means the same in $\mathbb{N}$ , $\mathbb{Z}$ and $\mathbb{Q}$ , so we never say where it is made. Every rule of Proposition 2.4.3 holds in $\mathbb{Q}$ , and $\mathbb{Q}_{>0} \mathrel{:=} \{ x \in \mathbb{Q} : x > 0 \}$ is $P_{\mathbb{Q}}$ .

One rule is new with fields, because rings have no inverses: taking reciprocals reverses the order of positive elements.

Proposition 3.2.2 (Reciprocals Reverse Order)

Let $F$ be an ordered field and $a, b \in F$ .

(a) If $a > 0$ , then $a^{-1} > 0$ .
(b) If $0 < a < b$ , then $0 < b^{-1} < a^{-1}$ , that is, $0 < 1/b < 1/a$ .

Idea. For (a), turn $a^{-1}$ into a product we can sign: $a^{-1} = a \cdot (a^{-1})^2$ , a positive element times a non-zero square. For (b), multiply $a < b$ by the positive element $a^{-1} b^{-1}$ : it cancels $a$ on the left and $b$ on the right, and swaps which reciprocal stands on which side.

Proof.

(a) Let $a > 0$ . Then $a \ne 0$ , so $a^{-1}$ exists, and $a^{-1} \ne 0$ by the Quick check after the uniqueness of inverses in Section 2.3. By Proposition 2.4.3 (e), $(a^{-1})^2 > 0$ . Now $a \cdot (a^{-1})^2 = (a a^{-1}) a^{-1} = 1 \cdot a^{-1} = a^{-1} ,$ and the left side is a product of two positive elements, so $a^{-1} > 0$ by (O4).
(b) Let $0 < a < b$ . Then $b > 0$ by (O2), so $a^{-1} > 0$ and $b^{-1} > 0$ by (a), and $c \mathrel{:=} a^{-1} b^{-1} > 0$ by (O4). Multiplying $a < b$ by $c > 0$ (Proposition 2.4.3 (c)) gives $b^{-1} = (a a^{-1}) b^{-1} = ac < bc = (b b^{-1}) a^{-1} = a^{-1} .$ Since $1/b = 1 \cdot b^{-1} = b^{-1}$ (Definition 2.3.1), this is $0 < 1/b < 1/a$ .

Quick check. Find non-zero $a, b \in \mathbb{Q}$ with $a < b$ and $1/a < 1/b$ . Which hypothesis of Proposition 3.2.2 (b) fails?

Solution. Take $a = -1$ and $b = 1$ . Then $1/a = -1$ , since $(-1)(-1) = 1$ , and $1/a = -1 < 1 = 1/b$ . The hypothesis $0 < a$ fails: (b) is about positive elements only.

3.2.3. Between two rationals

In $\mathbb{Z}$ every integer has a next one: there is no integer strictly between $m$ and $m + 1$ (Theorem 2.4.2 (c)). In $\mathbb{Q}$ the opposite holds. Let $2 \mathrel{:=} 1 + 1$ . By Proposition 2.4.3 (e) and (b), $1 > 0$ and $2 > 0$ , so $1/2 > 0$ by Proposition 3.2.2 (a). Now let $a < b$ in $\mathbb{Q}$ . Adding $a$ , and then $b$ , by (O3), $a + a < a + b < b + b ,$ and $a + a = (1 + 1)a = 2a$ , $b + b = 2b$ by distributivity. Multiplying by $1/2 > 0$ (Proposition 2.4.3 (c)) gives $a < \frac{a + b}{2} < b .$ So between two distinct rationals there is always a third, their midpoint. Applied with $a = 0$ : for every $x > 0$ , also $0 < x/2 < x$ . Hence $\mathbb{Q}_{>0}$ has no least element. In particular, well-ordering is a property of $\mathbb{N}$ (Theorem 1.3.3) that $\mathbb{Q}_{>0}$ does not share.

Warning. Between any two rationals lies another, but that does not mean every rational has a neighbor “right next to it”. It means the opposite: no rational $x$ has a next one, since any candidate $y > x$ is beaten by the midpoint of $x$ and $y$ . Phrases like “the rational just after $0$ ” name nothing.

Quick check. Find the midpoint of $1/3$ and $1/2$ , and confirm with the comparison formula that it lies strictly between them.

Solution. $1/3 + 1/2 = 5/6$ by Definition 3.1.2 ( $[(1 \cdot 2 + 1 \cdot 3, \, 6)]$ ), and $(5/6) \cdot (1/2) = 5/12$ . By Theorem 3.2.1 (a): $1/3 < 5/12$ because $1 \cdot 12 = 12 < 15 = 5 \cdot 3$ , and $5/12 < 1/2$ because $5 \cdot 2 = 10 < 12 = 1 \cdot 12$ .

3.2.4. The Archimedean property

Here is a statement so familiar that it seems not to need proof: every rational number is smaller than some natural number. For the real numbers it is a genuine theorem. Analysis on the Real Line, Chapter 1 obtains it from the least upper bound axiom, and there are ordered fields in which $\mathbb{N}$ is bounded above. For the constructed $\mathbb{Q}$ it is true for a simpler reason: every rational is a quotient of integers, and integers are as discrete as natural numbers.

Theorem 3.2.3 (The Rationals Are Archimedean)

For every $x \in \mathbb{Q}$ there is $n \in \mathbb{N}$ with $x < n$ .

Try it first (ten minutes): given $x = p/q$ with $q \in \mathbb{Z}_{>0}$ , which natural number beats it? Do not forget negative $p$ .

Idea. The first candidate is $p + 1$ , on the grounds that dividing by $q \ge 1$ “makes things smaller”, so $p/q \le p < p + 1$ . An attempt meets two obstacles. Dividing by $q \ge 1$ makes a negative number larger: $-3/2 > -3$ . And $p + 1$ is not a natural number when $p \le -2$ . Both disappear if we split on the sign of $p$ . A fraction with $p \le 0$ is at most $0$ , and $1$ beats it. For $p > 0$ the school intuition is right and provable: $q \ge 1$ gives $p \le pq$ , which the comparison formula reads as $p/q \le p$ .

Proof. Let $x \in \mathbb{Q}$ . By Proposition 3.1.4 (b), $x = p/q$ with $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ .

Case 1: $p \le 0$ . By Eq. 3.2.2, $p/q \le 0/1$ , since $p \cdot 1 \le 0 \cdot q$ . So $x \le 0 < 1$ (Proposition 2.4.3 (e)), and $n \mathrel{:=} 1 \in \mathbb{N}$ works.

Case 2: $p > 0$ . Then $p \in \mathbb{N}$ by Theorem 2.4.2 (b). Since $q > 0$ , discreteness (Theorem 2.4.2 (c), with $0 < q$ ) gives $1 \le q$ . Multiplying by $p > 0$ (Proposition 2.4.3 (c), or equality if $q = 1$ ) gives $p \cdot 1 \le p \cdot q$ . By Eq. 3.2.2 this says $p/q \le p/1 = p$ . Finally $p < p + 1$ by (O3), since $0 < 1$ . So $x \le p < p + 1$ , and $n \mathrel{:=} p + 1$ lies in $\mathbb{N}$ , because $\mathbb{N}$ is closed under addition. Hence $x < n$ .

In both cases $x < n$ for some $n \in \mathbb{N}$ , as claimed.

The $n$ found depends on the representative, and any one will do. The proof uses only $x = p/q$ , the comparison formula, and the ordered ring $\mathbb{Z}$ (discreteness, $\mathbb{N} = \{ x \in \mathbb{Z} : x \ge 0 \}$ ); no supremum appears. For the real numbers the same conclusion needs completeness.

The form in which later chapters of this volume use the property is about reciprocals: $1/n$ eventually falls below any positive rational.

Corollary 3.2.4 (Small Reciprocals in

\mathbb{Q}

)

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

Proof. Let $\varepsilon \in \mathbb{Q}_{>0}$ . By Proposition 3.2.2 (a), $1/\varepsilon > 0$ . By Theorem 3.2.3 there is $n \in \mathbb{N}$ with $1/\varepsilon < n$ . Then $n > 0$ , so $n \in \mathbb{Z}_{>0}$ (Theorem 2.4.2 (b)). By Proposition 3.2.2 (b) with $0 < 1/\varepsilon < n$ , $\frac{1}{n} < \frac{1}{1/\varepsilon} = \varepsilon ,$ where $1/(1/\varepsilon) = \varepsilon$ is $(a^{-1})^{-1} = a$ for $a = \varepsilon$ , the Quick check after the uniqueness of inverses in Section 2.3. If $m \ge n$ , then either $m = n$ , or $0 < n < m$ and $1/m < 1/n$ by Proposition 3.2.2 (b); in both cases $1/m \le 1/n < \varepsilon$ .

The order of the quantifiers is the point: $\varepsilon$ is given first, and $n$ is chosen after it and depends on $\varepsilon$ (Exercise A1 (e) swaps them). Chapter 4 uses the corollary in exactly this form, with $\varepsilon \in \mathbb{Q}_{>0}$ .

3.2.5. The integer part

By Theorem 3.2.3, every rational lies below an integer. With the least-element property of $\mathbb{Z}$ , it pins every rational between two consecutive integers.

Proposition 3.2.5 (Integer Part of a Rational)

For every $x \in \mathbb{Q}$ there is exactly one $m \in \mathbb{Z}$ with $m \le x < m + 1$ . It is called the integer part of $x$ and written $\left\lfloor x \right\rfloor$ .

Idea. The integer just above $x$ should be the least integer exceeding $x$ . So look at the set of integers that exceed $x$ : Theorem 3.2.3 makes it non-empty, and applied to $-x$ it bounds the set below, so Proposition 2.4.4 hands us its least element. One less than that is the integer part. Uniqueness is discreteness: two candidates one unit apart cannot both fit below $x$ and above $x - 1$ .

Proof. Let $x \in \mathbb{Q}$ , and let $S \mathrel{:=} \{ k \in \mathbb{Z} : x < k \}$ . By Theorem 3.2.3 there is $n \in \mathbb{N} \subseteq \mathbb{Z}$ with $x < n$ , so $S \ne \emptyset$ . Applying Theorem 3.2.3 to $-x$ gives $n' \in \mathbb{N}$ with $-x < n'$ , that is, $-n' < x$ (Proposition 2.4.3 (a)). Every $k \in S$ then has $-n' < x < k$ , so the integer $-n'$ is a lower bound of $S$ . By Proposition 2.4.4, $S$ has a least element $l$ . Let $m \mathrel{:=} l - 1 \in \mathbb{Z}$ , so that $l = m + 1$ .

Existence. $x < l = m + 1$ , since $l \in S$ . And $m \notin S$ : otherwise $l \le m = l - 1 < l$ , so $l < l$ , against (O1). So $x < m$ fails, and $m \le x$ by totality (Proposition 2.4.3 (i)).

Uniqueness. Let $m, m' \in \mathbb{Z}$ both satisfy the condition, and suppose $m < m'$ . By discreteness (Theorem 2.4.2 (c)), $m + 1 \le m'$ . Then $m' \le x < m + 1 \le m'$ , so $m' < m'$ , against (O1). By symmetry $m' < m$ is impossible too, so $m = m'$ by (O1).

The comparisons in this proof mix integers and rationals ( $x < k$ ); by Theorem 3.2.1 (b) the two orders agree on $\mathbb{Z}$ . For $a \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ , $\left\lfloor a/n \right\rfloor$ is the quotient in Section 2.5’s division of $a$ by $n$ (Exercise B3).

Quick check. Compute $\left\lfloor -7/3 \right\rfloor$ . Then find the least $n \in \mathbb{Z}_{>0}$ with $1/n < 3/1000$ .

Solution. $\left\lfloor -7/3 \right\rfloor = -3$ : by Eq. 3.2.2, $-3 = -3/1 \le -7/3$ because $(-3) \cdot 3 = -9 \le -7$ , and $-7/3 < -2$ because $-7 < -6 = (-2) \cdot 3$ (Theorem 3.2.1 (a)). Not $-2$ : the rule “drop the fraction” gives $\left\lfloor x \right\rfloor$ for $x \ge 0$ , but not for negative non-integers such as $-7/3$ .

For $n \in \mathbb{Z}_{>0}$ , the comparison formula gives $1/n < 3/1000$ if and only if $1 \cdot 1000 < 3n$ . Since $3 \cdot 333 = 999 < 1000$ and $3 \cdot 334 = 1002 > 1000$ , the least such $n$ is $334$ (for $n \le 333$ , $3n \le 999$ ).

3.2.6. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 3.2.1 and about Corollary 3.2.4.

(a) Where in the proof (including the well-definedness check before it) is $q > 0$ used? What goes wrong without it?
(b) Why does (P2) need “exactly one” of $x \in P_{\mathbb{Q}}$ , $x = 0$ , $-x \in P_{\mathbb{Q}}$ , and not just “at least one”?
(c) Run the comparison formula on $-2/3$ and $-3/5$ : which is larger?
(d) State the idea of the proof in two sentences.
(e) Write Corollary 3.2.4 (its first sentence) in symbols. Then write the version with the two quantifiers swapped, negate it, and decide which of the two versions is true.

Solution.

(a) Three times: in the well-definedness check, $q, q' > 0$ turn $p > 0$ into $p' > 0$ ; in (P1), $ps > 0$ and $rq > 0$ need $s > 0$ and $q > 0$ ; in (a), the difference $r/s - p/q$ has denominator $qs > 0$ , so its sign is the sign of its numerator. Without it, the non-example after Definition 3.2.1 shows both failures: $(1, 1) \approx (-1, -1)$ gives two verdicts for one class, and “ $ps < rq$ ” gives $0 < 1$ for $(0, 1), (1, 1)$ but $0 < -1$ for $(0, 1), (-1, -1)$ .
(b) “At least one” would allow a non-zero $x$ with both $x$ and $-x$ positive, and then $x < 0$ and $0 < x$ at once, against (O1). The “at most one” half is what makes the order antisymmetric; Proposition 2.4.1 uses it to get trichotomy (O1).
(c) By Theorem 3.2.1 (a), $-2/3 < -3/5$ if and only if $(-2) \cdot 5 < (-3) \cdot 3$ , that is, $-10 < -9$ , which is true. So $-3/5$ is the larger.
(d) By Proposition 2.4.1 it is enough to show that the positive set is closed under $+$ and $\cdot$ and satisfies the trichotomy (P2). Each of these, run on representatives with positive denominators, is a statement about integer numerators, which holds because $\mathbb{Z}$ is an ordered ring.
(e) The corollary: $\forall \varepsilon \in \mathbb{Q}_{>0} \ \exists n \in \mathbb{Z}_{>0} \ \ 1/n < \varepsilon$ . Swapped: $\exists n \in \mathbb{Z}_{>0} \ \forall \varepsilon \in \mathbb{Q}_{>0} \ \ 1/n < \varepsilon$ , “one $n$ works for every $\varepsilon$ ”. By Logic and Proof, Proposition 6.2.3 (the bounded form of Logic and Proof, Proposition 6.2.1), applied twice, its negation is $\forall n \in \mathbb{Z}_{>0} \ \ \exists \varepsilon \in \mathbb{Q}_{>0} \ \ \neg (1/n < \varepsilon) .$ This negation is true: given $n \in \mathbb{Z}_{>0}$ , take $\varepsilon \mathrel{:=} 1/n$ , which lies in $\mathbb{Q}_{>0}$ by Proposition 3.2.2 (a), and $1/n < 1/n$ fails by (O1). So the swapped version is false, and the corollary (proved above) is true. The $n$ must be allowed to depend on $\varepsilon$ .

B. Practice

Exercise (B1: A rational of the form a + 1/n)

(a) Let $a, b \in \mathbb{Q}$ with $a < b$ . Prove that there is $n \in \mathbb{Z}_{>0}$ with $a < a + 1/n < b$ , and that every $m \in \mathbb{Z}$ with $m \ge n$ works too.
(b) Find the least such $n$ for $a = 1/3$ and $b = 1/2$ .

Solution.

(a) Let $\varepsilon \mathrel{:=} b - a$ . Then $\varepsilon > 0$ by Proposition 2.4.3 (a), so Corollary 3.2.4 gives $n \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ , and $1/m < \varepsilon$ for every $m \ge n$ . Fix such an $m$ (for instance $m = n$ ). Adding $a$ (O3): $a + 1/m < a + (b - a) = b$ . And $1/m > 0$ by Proposition 3.2.2 (a), since $m > 0$ ; adding $a$ gives $a < a + 1/m$ .
(b) Here $b - a = 1/2 - 1/3 = 1/6$ , and for $n \in \mathbb{Z}_{>0}$ the comparison formula gives $1/n < 1/6$ if and only if $6 < n$ . So the least $n$ is $7$ , and $a + 1/7 = 1/3 + 1/7 = 10/21$ . Check: $1/3 < 10/21$ since $21 < 30$ , and $10/21 < 1/2$ since $20 < 21$ . For $n = 6$ , $a + 1/6 = 1/2 = b$ , which is not strictly below $b$ .

Exercise (B2)

Compute $\left\lfloor 22/7 \right\rfloor$ , $\left\lfloor -22/7 \right\rfloor$ , $\left\lfloor 0 \right\rfloor$ and $\left\lfloor -1/100 \right\rfloor$ , and check each against the defining inequalities of Proposition 3.2.5.

Solution. We use Eq. 3.2.2 and the comparison formula with denominators $1$ for the integers.

$\left\lfloor 22/7 \right\rfloor = 3$ : $3 \le 22/7$ since $3 \cdot 7 = 21 \le 22$ , and $22/7 < 4$ since $22 < 28 = 4 \cdot 7$ .
$\left\lfloor -22/7 \right\rfloor = -4$ : $-4 \le -22/7$ since $-28 \le -22$ , and $-22/7 < -3$ since $-22 < -21$ .
$\left\lfloor 0 \right\rfloor = 0$ : $0 \le 0 < 1$ .
$\left\lfloor -1/100 \right\rfloor = -1$ : $-1 \le -1/100$ since $-100 \le -1$ , and $-1/100 < 0$ since $-1 < 0$ .

The first two show that $\left\lfloor -x \right\rfloor \ne -\left\lfloor x \right\rfloor$ in general: $\left\lfloor 22/7 \right\rfloor = 3$ , but $\left\lfloor -22/7 \right\rfloor = -4$ , not $-3$ .

Exercise (B3: The quotient is the integer part)

Let $a \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ , and let $q, r$ be the quotient and remainder of Theorem 2.5.2 (a), so $a = qn + r$ with $0 \le r < n$ . Prove that $q = \left\lfloor a/n \right\rfloor$ , and hence $r = a - n \left\lfloor a/n \right\rfloor$ .

Solution. From the hypothesis, $0 \le r < n$ ; adding $qn$ (Proposition 2.4.3 (b)) gives $qn \le a < qn + n .$ These are inequalities between integers, and by Theorem 3.2.1 (b) and Proposition 3.1.4 they hold in $\mathbb{Q}$ as well, with the same sums and products. In $\mathbb{Q}$ , $n > 0$ , so $n^{-1} > 0$ (Proposition 3.2.2 (a)). Multiplying by $n^{-1}$ preserves strict inequalities (Proposition 2.4.3 (c)) and equalities, so $q = qn \cdot n^{-1} \le a \cdot n^{-1} < (qn + n) \cdot n^{-1} = q + 1 .$ That is, $q \le a/n < q + 1$ , with $q \in \mathbb{Z}$ . By the uniqueness in Proposition 3.2.5, $q = \left\lfloor a/n \right\rfloor$ , and then $r = a - qn = a - n \left\lfloor a/n \right\rfloor$ .

Exercise (B4: Prove or disprove)

Prove each true statement and refute each false one with a counterexample.

(a) If $x, y \in \mathbb{Q}$ and $0 < x < y$ , then $1/x - 1/y < y - x$ .
(b) For every $x \in \mathbb{Q}_{>0}$ there is $n \in \mathbb{Z}_{>0}$ with $1/n < x < n$ .
(c) Every non-empty $S \subseteq \mathbb{Q}$ that has a positive lower bound has a least element.
(d) For every $x \in \mathbb{Q}$ , $\left\lfloor x + 1 \right\rfloor = \left\lfloor x \right\rfloor + 1$ .

Solution.

(a) False. Take $x = 1/2$ and $y = 1$ . Then $0 < x < y$ , but $1/x - 1/y = 2 - 1 = 1$ and $y - x = 1/2$ , and $1 > 1/2$ .
(b) True. By Theorem 3.2.3 there is $n_1 \in \mathbb{N}$ with $x < n_1$ . By Corollary 3.2.4 there is $n_2 \in \mathbb{Z}_{>0}$ with $1/m < x$ for every $m \in \mathbb{Z}$ with $m \ge n_2$ . Let $n$ be the larger of $n_1$ and $n_2$ (totality, Proposition 2.4.3 (i)). Then $n \ge n_2 > 0$ , so $n \in \mathbb{Z}_{>0}$ and $1/n < x$ ; and $x < n_1 \le n$ .
(c) False. The set $S \mathrel{:=} \{ x \in \mathbb{Q} : 1 < x \}$ is non-empty ( $2 \in S$ ) and has the positive lower bound $1$ . For $x \in S$ , the midpoint $(1 + x)/2$ lies strictly between $1$ and $x$ (the midpoint paragraph of this section), so it is in $S$ and smaller than $x$ . No element of $S$ is least. A positive lower bound does not help: $\mathbb{Q}$ is not $\mathbb{Z}$ .
(d) True. Let $m \mathrel{:=} \left\lfloor x \right\rfloor$ , so $m \le x < m + 1$ . Adding $1$ (O3) gives $m + 1 \le x + 1 < (m + 1) + 1$ , with $m + 1 \in \mathbb{Z}$ . By the uniqueness in Proposition 3.2.5, $\left\lfloor x + 1 \right\rfloor = m + 1$ .

C. Going deeper

Exercise (C1: Exit check:

\mathbb{Q}

is Archimedean)

Prove, from the construction of $\mathbb{Q}$ and the results of this chapter before Theorem 3.2.3 (and not from any fact about the real numbers), that for every $x \in \mathbb{Q}$ there is $n \in \mathbb{N}$ with $x < n$ ; and deduce that for every $\varepsilon \in \mathbb{Q}_{>0}$ there is $n \in \mathbb{Z}_{>0}$ with $1/n < \varepsilon$ .

Solution. The theorem. Let $x \in \mathbb{Q}$ . By Proposition 3.1.4 (b), $x = p/q$ with $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ .

If $p \le 0$ , then $p \cdot 1 \le 0 \cdot q$ , so $x = p/q \le 0/1 = 0$ by the comparison formula (Theorem 3.2.1 (a), with equality by Proposition 3.1.4 (b)). Hence $x \le 0 < 1$ , and $n = 1$ works.

If $p > 0$ , then $p \in \mathbb{N}$ (Theorem 2.4.2 (b)), and $q \ge 1$ by discreteness (Theorem 2.4.2 (c)), since $q > 0$ . Multiplying $1 \le q$ by $p > 0$ (Proposition 2.4.3 (c), or equality if $q = 1$ ) gives $p \le pq$ , which by the comparison formula says $p/q \le p/1$ . So $x \le p < p + 1$ , and $n \mathrel{:=} p + 1 \in \mathbb{N}$ works.

The corollary. Let $\varepsilon \in \mathbb{Q}_{>0}$ be given. Then $1/\varepsilon > 0$ (Proposition 3.2.2 (a)), and the theorem gives $n \in \mathbb{N}$ with $1/\varepsilon < n$ ; in particular $n > 0$ , so $n \in \mathbb{Z}_{>0}$ . By Proposition 3.2.2 (b), $1/n < 1/(1/\varepsilon) = \varepsilon$ . The $n$ depends on $\varepsilon$ , which was fixed first.

Marking scheme. (10 points) - 1: writes $x = p/q$ with $p \in \mathbb{Z}$ , $q \in \mathbb{Z}_{>0}$ , citing the representation of rationals. - 2: the case $p \le 0$ : $x \le 0 < 1$ , justified by the comparison formula. - 3: the case $p > 0$ : $q \ge 1$ by discreteness of $\mathbb{Z}$ , and $p/q \le p$ by the comparison formula (or an equivalent inequality argument from the ordered-field rules). - 1: exhibits $n \in \mathbb{N}$ (for instance $p + 1$ ) and checks $x < n$ . - 3: the corollary: $\varepsilon$ fixed first, $n > 1/\varepsilon$ from the theorem, reciprocals reverse order. Fatal errors (0 for the step): no separate treatment of $p < 0$ (there “ $p/q \le p$ ” fails once $q \ge 2$ , as $-3/2 > -3$ shows, and $p + 1 \notin \mathbb{N}$ once $p \le -2$ ); using a supremum, the real numbers, or “the decimal expansion of $x$ ”. A route through Proposition 3.2.5 is circular here (its proof uses the theorem) and earns nothing for the theorem’s 7 points; the corollary’s 3 points, deduced from the theorem as stated, can still be earned.

Exercise (C2: The comparison, on representatives)

The comparison formula of Theorem 3.2.1 (a) was proved through the positive set. Prove directly that the relation “ $ps < rq$ ” on pairs in $\mathbb{Z} \times \mathbb{Z}_{>0}$ does not depend on the representatives: if $(p, q) \sim (p', q')$ and $(r, s) \sim (r', s')$ , then $ps < rq$ if and only if $p's' < r'q'$ .

Here is the start.

We change one argument at a time. First argument: let $(p, q) \sim (p', q')$ and $ps < rq$ ; we must show $p's < rq'$ .

…

Name the move, then complete it.

Solution. The move is check on representatives, one argument at a time: change the first pair with the second fixed, then the second with the first fixed, and join the two by transitivity of $\iff$ .

First argument. Let $pq' = p'q$ and $ps < rq$ . Multiply by $q' > 0$ (Proposition 2.4.3 (c)): $psq' < rqq'$ . The left side is $(pq')s = (p'q)s = (p's)q$ , and the right side is $(rq')q$ . So $(p's)q < (rq')q$ . If $p's \ge rq'$ , then multiplying by $q > 0$ would give $(p's)q \ge (rq')q$ (Proposition 2.4.3 (c), or equality), against (O1). So $p's < rq'$ . Since $\sim$ is symmetric, the same argument with the roles of $(p, q)$ and $(p', q')$ exchanged gives the converse: $ps < rq \iff p's < rq'$ .

Second argument. Let $rs' = r's$ , and fix $(p', q')$ . If $p's < rq'$ , multiply by $s' > 0$ : $p'ss' < rq's'$ , and $rs' = r's$ turns the right side into $(r's)q' = (r'q')s$ . So $(p's')s < (r'q')s$ , and canceling $s > 0$ as above gives $p's' < r'q'$ . By symmetry again, $p's < rq' \iff p's' < r'q'$ .

Join. Chaining the two equivalences, $ps < rq \iff p's < rq' \iff p's' < r'q' .$ This proves the claim. By Theorem 3.2.1 (a) both sides also mean $p/q < r/s$ ; the point of the exercise is that the integer relation alone is already independent of the representatives, and positivity of $q, q', s, s'$ is used at every multiplication and cancellation.

Marking scheme. (10 points) - 2: names the move (check on representatives, one argument at a time, joined by transitivity of $\iff$ ). - 3: first argument: multiplies $ps < rq$ by $q' > 0$ , uses $pq' = p'q$ to reach $(p's)q < (rq')q$ , cancels $q > 0$ (by contradiction via trichotomy), and gets the converse from symmetry of $\sim$ . - 3: second argument: the same with $s' > 0$ , $rs' = r's$ and cancellation of $s > 0$ , with the converse by symmetry. - 2: chains $ps < rq \iff p's < rq' \iff p's' < r'q'$ and says where positivity of $q, q', s, s'$ is used. Fatal errors (0 for the step): multiplying or canceling by a denominator without using its sign; proving only one direction of an equivalence without invoking symmetry; using $p/q < r/s$ (the comparison formula of Theorem 3.2.1 (a)) instead of working on the integer relation.

Exercise (C3: Find the error)

Here is an argument for Theorem 3.2.3. Is the conclusion true? Is the argument correct? If not, name the first line that fails, say what makes it illegal, and give a counterexample to the step.

Let $x \in \mathbb{Q}$ , and write $x = p/q$ with $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ . (2) Then $q \ge 1$ , by discreteness of $\mathbb{Z}$ . (3) So $x = p/q \le p$ , since dividing by a number at least $1$ cannot increase it. (4) Hence $n \mathrel{:=} p + 1$ is a natural number with $n > x$ .

Solution. The conclusion is true: it is Theorem 3.2.3. The argument is not correct.

The failing line is (3). It cites the general “fact” that $p/q \le p$ whenever $q \ge 1$ . That is neither proved in this chapter nor true, so the line rests on nothing: entry (N9) of Logic and Proof, Example (What is not allowed). What is true, and what the proof of the theorem uses, is the special case $p \ge 0$ .

Counterexample to the step. $p = -3$ , $q = 2$ : then $q \ge 1$ , but $x = -3/2 > -3 = p$ . Indeed the comparison formula gives $-3/1 < -3/2$ , because $(-3) \cdot 2 = -6 < -3 = (-3) \cdot 1$ . There is no counterexample to the conclusion.

A second failing line. Line (4) also fails for $p \le -2$ : then $p + 1 \le -1$ , which is not in $\mathbb{N} = \{ n \in \mathbb{Z} : n \ge 0 \}$ (Theorem 2.4.2 (b)). For $p = -1$ , $n = 0$ happens to work, because $x < 0$ ; but the stated reason “ $x \le p$ ” still fails there once $q \ge 2$ .

Repair. Split on the sign of $p$ , as the proof of Theorem 3.2.3 does: for $p \le 0$ , $x \le 0 < 1$ ; for $p > 0$ , line (3) is correct, with the comparison formula as its reason ( $p \cdot 1 \le p \cdot q$ ).

Marking scheme. (10 points) - 2: says that the conclusion is true and the argument is not correct. - 3: names line (3), and the unproved general claim “ $p/q \le p$ for $q \ge 1$ ” (entry (N9)) as what makes it illegal. - 2: gives a counterexample to the step with $p < 0$ and $q \ge 2$ , checked by the comparison formula. - 1: notes that line (4) fails as well for $p \le -2$ . - 2: repairs the argument by a case split on the sign of $p$ . Fatal errors (0 for the step): declaring the conclusion false; offering a counterexample to the conclusion.

Exercise (C4: Division from the integer part)

Let $a \in \mathbb{Z}$ and $n \in \mathbb{Z}_{>0}$ . Prove the existence half of Theorem 2.5.2 (a) directly from Proposition 3.2.5, without the least-element argument of the proof in Section 2.5: put $q \mathrel{:=} \left\lfloor a/n \right\rfloor$ and $r \mathrel{:=} a - qn$ , and show that $0 \le r < n$ . Say where $n > 0$ is used.

Solution. By Proposition 3.2.5, $q \mathrel{:=} \left\lfloor a/n \right\rfloor \in \mathbb{Z}$ satisfies $q \le a/n < q + 1$ in $\mathbb{Q}$ , where $a/n = a \cdot n^{-1}$ and $n \ne 0$ in $\mathbb{Q}$ . Since $n > 0$ , multiplying by $n$ preserves the strict inequality (Proposition 2.4.3 (c)) and the equality case, so $qn \le (a \cdot n^{-1}) \cdot n = a < (q + 1)n = qn + n .$ Subtracting $qn$ (that is, adding $-qn$ , (O3)) gives $0 \le a - qn < n$ . Here $r \mathrel{:=} a - qn$ is an integer, and by Theorem 3.2.1 (b) and Proposition 3.1.4 ( $j$ preserves sums and products, so $j(a) - j(q)j(n) = j(a - qn)$ ) the inequalities $0 \le r < n$ , proved in $\mathbb{Q}$ , hold in $\mathbb{Z}$ . So $a = qn + r$ with $0 \le r < n$ .

The hypothesis $n > 0$ is used when multiplying by $n$ : for $n < 0$ , multiplication reverses inequalities (Proposition 2.4.3 (d)), and the same $q$ would give $qn \ge a > qn + n$ , so $n < r \le 0$ instead. (This exercise is practice with a result already proved; nothing later rests on it.)

Marking scheme. (10 points) - 2: states $q \le a/n < q + 1$ from Proposition 3.2.5. - 3: multiplies by $n > 0$ , treating both the strict inequality and the equality case. - 2: subtracts $qn$ to get $0 \le a - qn < n$ . - 1: moves the inequalities back to $\mathbb{Z}$ for the integer $r = a - qn$ . - 2: says where $n > 0$ is used, with the reversed inequalities when $n < 0$ . Fatal errors (0 for the step): using the existence half of Theorem 2.5.2 or its least-element proof (circular here); multiplying the inequalities by $n$ without using $n > 0$ .