2.5 The Rationals as an Ordered Field; the Archimedean Property

Section 2.4 built $\mathbb{Q}$ as a set of classes of fractions and proved that it is a field (Theorem 2.4.3): we can add, subtract, multiply, and divide by anything non-zero. What it did not give us is an order. In school one “sees” that $-3/5 < -7/12$ by placing both on a line, but the line is the school picture this volume has set aside, so the order must be defined on the classes and its rules proved. This section does that, by the method of Section 2.3: name the positive rationals, check two closure properties, and let Proposition 2.3.3 produce the rest. Then we prove the first fact about $\mathbb{Q}$ that later chapters of this volume lean on at every turn: every rational is exceeded by a natural number, and so $1/n$ eventually drops below any positive rational. Finally every rational gets an integer part.

2.5.1. Which fractions are positive

Throughout, a rational is written as in Section 2.4. By Proposition 2.4.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.3.3), and Proposition 2.3.3 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 2.4.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 2.5.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.3.2, $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.3.4 (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.3.5 (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 .

(2.5.1)

Examples. The class $3/4$ lies in $P_{\mathbb{Q}}$ , and so does $6/8$ , the same class: both numerators are positive, as Eq. 2.5.1 says they must be. The class $-6/8$ does not, since $-6 > 0$ fails. The degenerate case is zero: $0 = 0/1 = 0/7$ , and $0 > 0$ fails, so $0 \notin P_{\mathbb{Q}}$ . That matters, because (P2) of Proposition 2.3.3 will ask for exactly one of $x \in P_{\mathbb{Q}}$ , $x = 0$ , $-x \in P_{\mathbb{Q}}$ .

Non-example by minimal change. Allow negative denominators, as in Example (Non-zero denominators give the same rationals), and keep the test “the numerator is positive”. The relation is the same and still an equivalence relation, but now $(1, 1) \approx (-1, -1)$ : the class of $(1, 1)$ passes the test with one representative and fails it with another. The clause that fails is the hypothesis of Theorem 2.2.1 (c), and the step of the check above that breaks is “ $q > 0$ ”.

Why this definition. With non-zero denominators of either sign one could test “ $pq > 0$ ” instead, which is well defined; the price is a product in every sign test and two sign cases in every proof. Positive denominators put all the sign information in one integer. The order is defined through the positive set rather than through a formula for $x < y$ , so that Proposition 2.3.3 does the work of (O1)–(O4) once and for all.

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. 2.5.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}}$ .)

2.5.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 2.5.1 (The Rationals Form an Ordered Field)

With the order of Definition 2.5.1, $\mathbb{Q}$ is an ordered field (Definition 2.3.2), 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. By Proposition 2.3.3, a commutative ring with a positive set satisfying (P1) and (P2) is an ordered commutative ring, and $\mathbb{Q}$ is already a field. So everything reduces to the two properties of $P_{\mathbb{Q}}$ , and Eq. 2.5.1 turns each into a statement about numerators in $\mathbb{Z}$ : reduce to the level below. A sum $p/q + r/s$ has numerator $ps + rq$ , and with $p, r > 0$ this is positive because $s$ and $q$ are. The comparison formula is (P1)’s computation run on a difference. Before reading on: where is $q > 0$ used?

Proof. By Theorem 2.4.3, $\mathbb{Q}$ is a field, in particular a commutative ring. We check (P1) and (P2) of Proposition 2.3.3 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. 2.5.1, $p > 0$ and $r > 0$ ; and $q, s > 0$ by Theorem 2.3.4 (b). By Definition 2.4.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.3.5 (b); and $pr > 0$ by (O4). By Eq. 2.5.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 2.4.2). By Theorem 2.4.3, the zero of $\mathbb{Q}$ is $[(0, 1)]$ , and $x = 0$ if and only if $p = 0$ . By Eq. 2.5.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.3.5 (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.3.3, the relation $x < y \iff y - x \in P_{\mathbb{Q}}$ , which is the relation of Definition 2.5.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.3.2).

(a) Let $p, r \in \mathbb{Z}$ and $q, s \in \mathbb{Z}_{>0}$ . By Definition 2.4.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. 2.5.1, since $qs \in \mathbb{Z}_{>0}$ ), if and only if $rq - ps > 0$ , which by Proposition 2.3.5 (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 2.4.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: $q > 0$ is used three times. In the well-definedness check before Eq. 2.5.1, the positive $q$ and $q'$ carry the sign from $p$ to $p'$ . In (P1), $ps$ and $rq$ are positive because $s$ and $q$ are. In (a), the difference has denominator $qs$ , a positive integer, so that Eq. 2.5.1 can read its sign off the numerator. Without positive denominators the first of these fails outright (the non-example above), and so does the comparison formula: see the warning after Example (Non-zero denominators give the same rationals).

Since $p/q = r/s$ exactly when $ps = rq$ (Proposition 2.4.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 .

(2.5.2)

By (b), the order of $\mathbb{Q}$ restricted to $\mathbb{Z}$ is the order of $\mathbb{Z}$ , which in turn restricts to the order of $\mathbb{N}$ (Theorem 2.3.4 (a)). So after the identifications $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q}$ , a comparison of two integers means the same thing in all three sets, and we never need to say where it is made. Every rule of Proposition 2.3.5 now holds in $\mathbb{Q}$ , and we write $\mathbb{Q}_{>0} \mathrel{:=} \{ x \in \mathbb{Q} : x > 0 \}$ for the set of positive rationals, which is $P_{\mathbb{Q}}$ .

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

Proposition 2.5.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$ : otherwise $1 = a a^{-1} = a \cdot 0 = 0$ (Proposition 2.3.2 (b)), against $1 \ne 0$ in a field. By Proposition 2.3.5 (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.3.5 (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$ .

2.5.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.3.4 (c)). In $\mathbb{Q}$ the opposite holds. Let $2 \mathrel{:=} 1 + 1$ . By Proposition 2.3.5 (e) and (b), $1 > 0$ and $2 > 0$ , so $1/2 > 0$ by Proposition 2.5.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.3.5 (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.6.2) 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 2.4.2 ( $[(1 \cdot 2 + 1 \cdot 3, \, 6)]$ ), and $(5/6) \cdot (1/2) = 5/12$ . By Theorem 2.5.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$ .

2.5.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, built from rational functions, in which the natural numbers are 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 2.5.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 2.4.4 (b), $x = p/q$ with $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ .

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

Case 2: $p > 0$ . Then $p \in \mathbb{N}$ by Theorem 2.3.4 (b). Since $q > 0$ , discreteness (Theorem 2.3.4 (c), with $0 < q$ ) gives $1 \le q$ . Multiplying by $p > 0$ (Proposition 2.3.5 (c), or equality if $q = 1$ ) gives $p \cdot 1 \le p \cdot q$ . By Eq. 2.5.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 $x$ , through the numerator of the representative used; a different representative may give a different $n$ , and any one will do. The proof uses only the representation $x = p/q$ , the comparison formula, and elementary facts about the ordered ring $\mathbb{Z}$ (discreteness, $\mathbb{N} = \{ x \in \mathbb{Z} : x \ge 0 \}$ , the rules for inequalities) and about $\mathbb{N}$ . No supremum is mentioned in it. That is the contrast with the real numbers, where the same conclusion needs the completeness axiom.

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

Corollary 2.5.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 2.5.2 (a), $1/\varepsilon > 0$ . By Theorem 2.5.3 there is $n \in \mathbb{N}$ with $1/\varepsilon < n$ . Then $n > 0$ , so $n \in \mathbb{Z}_{>0}$ (Theorem 2.3.4 (b)). By Proposition 2.5.2 (b) with $0 < 1/\varepsilon < n$ , $\frac{1}{n} < \frac{1}{1/\varepsilon} = \varepsilon ,$ where $1/(1/\varepsilon) = \varepsilon$ because $\varepsilon$ is a multiplicative inverse of $\varepsilon^{-1}$ , and inverses are unique (if $bc = 1 = bc'$ , then $c = c(bc') = (cb)c' = c'$ ). If $m \ge n$ , then either $m = n$ , or $0 < n < m$ and $1/m < 1/n$ by Proposition 2.5.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 asks what happens if the order is swapped. Here $\varepsilon$ is a rational number, because the real numbers have not yet been constructed, and the corollary is the form in which a later chapter of this volume uses the Archimedean property, with $\varepsilon \in \mathbb{Q}_{>0}$ .

2.5.5. The integer part

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

Proposition 2.5.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 2.5.3 makes it non-empty, and applied to $-x$ it bounds the set below, so Proposition 2.3.6 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 2.5.3 there is $n \in \mathbb{N} \subseteq \mathbb{Z}$ with $x < n$ , so $S \ne \emptyset$ . Applying Theorem 2.5.3 to $-x$ gives $n' \in \mathbb{N}$ with $-x < n'$ , that is, $-n' < x$ (Proposition 2.3.5 (a)). Every $k \in S$ then has $-n' < x < k$ , so the integer $-n'$ is a lower bound of $S$ . By Proposition 2.3.6, $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.3.5 (i)).

Uniqueness. Let $m, m' \in \mathbb{Z}$ both satisfy the condition, and suppose $m < m'$ . By discreteness (Theorem 2.3.4 (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$ ), and the least element is taken in $\mathbb{Z}$ ; by Theorem 2.5.1 (b) the two orders agree on $\mathbb{Z}$ , so nothing is lost. A later chapter of this volume reads $\left\lfloor p/q \right\rfloor$ , for $q \in \mathbb{Z}_{>0}$ , as the quotient in the division of $p$ by $q$ .

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. 2.5.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 2.5.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$ ).

2.5.6. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the proof of Theorem 2.5.1 and about Corollary 2.5.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 2.5.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 test “numerator positive” is not well defined: in the non-example after Definition 2.5.1, $(1, 1) \approx (-1, -1)$ gives two verdicts for one class, and, as the warning after Example (Non-zero denominators give the same rationals) shows, “ $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.3.3 uses it to get trichotomy (O1).
(c) By Theorem 2.5.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.3.3 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 2.5.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)

Put $-7/12$ , $-3/5$ and $-4/7$ in increasing order, using only the comparison formula.

Solution. By Theorem 2.5.1 (a), pair by pair:

$-3/5 < -7/12$ , since $(-3) \cdot 12 = -36 < -35 = (-7) \cdot 5$ ;
$-7/12 < -4/7$ , since $(-7) \cdot 7 = -49 < -48 = (-4) \cdot 12$ ;
$-3/5 < -4/7$ , since $(-3) \cdot 7 = -21 < -20 = (-4) \cdot 5$ .

Hence $-3/5 < -7/12 < -4/7$ . (The third comparison follows from the first two by (O2); computing it is a check.)

Exercise (B2: 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.3.5 (a), so Corollary 2.5.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 2.5.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 (B3)

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 2.5.5.

Solution. We use Eq. 2.5.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$ .

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 2.5.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 2.4.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 2.5.1 (a), with equality by Proposition 2.4.4 (b)). Hence $x \le 0 < 1$ , and $n = 1$ works.

If $p > 0$ , then $p \in \mathbb{N}$ (Theorem 2.3.4 (b)), and $q \ge 1$ by discreteness (Theorem 2.3.4 (c)), since $q > 0$ . Multiplying $1 \le q$ by $p > 0$ (Proposition 2.3.5 (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 2.5.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 2.5.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 2.5.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 2.5.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.3.5 (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.3.5 (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 2.5.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 2.5.1 (a)) instead of working on the integer relation.

Exercise (C3: Find the error)

Here is an argument for Theorem 2.5.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 2.5.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.3.4 (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 2.5.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.