The Lumenary · Early undergraduate

Constructing ℤ, ℚ and ℝ

Name: ______________________

Date: ______________________

You will learn to

Construct $\Z$ as equivalence classes of pairs of natural numbers, prove that addition and multiplication are well defined, and identify the result with the integers
Construct $\Q$ as the field of fractions of $\Z$ , and explain exactly where the absence of zero divisors is needed
Construct $\R$ from Dedekind cuts and prove the least-upper-bound property; describe the alternative construction from Cauchy sequences
State the uniqueness of the complete ordered field, prove that such a field is Archimedean, and outline why any two are isomorphic
Explain what the constructions prove (that structures with the required properties exist) and what they do not

1.
With $(a, b) \sim (c, d)$ iff $a + d = c + b$ , which pairs of natural numbers lie in the class that represents the integer $-2$ ? (Choose all that apply.)
- A. $(0, 2)$
- B. $(5, 3)$
- C. $(3, 5)$
- D. $(10, 12)$
- E. $(2, 0)$
2.
Using $[(a, b)] \cdot [(c, d)] = [(ac + bd,\, ad + bc)]$ , compute $[(3, 5)] \cdot [(4, 1)]$ . Which integer does the resulting class represent?
3.
In the proof that equality of fractions ( $ad = cb$ ) is transitive, from $ad = cb$ and $cf = ed$ we derive $(af)d = (eb)d$ . Which step needs the hypothesis that the ring has no zero divisors?
- A.Concluding $af = eb$ from $(af)d = (eb)d$ and $d \neq 0$
- B.Rewriting $(af)d = (ad)f$
- C.Substituting $ad = cb$
- D.Reflexivity, $ab = ab$
4.
Each rule below is defined on a representative $a/b$ (or two, $a/b$ and $c/d$ ) of a rational number, with $b, d \neq 0$ . Which rules are not well defined as functions of the rational numbers? (Choose all that apply.)
- A. $(a/b, c/d) \mapsto (a + c)/(b + d)$
- B. $(a/b, c/d) \mapsto (ad + cb)/(bd)$
- C. $a/b \mapsto b/a$ , for $a \neq 0$
- D. $a/b \mapsto a + b$
- E. $a/b \mapsto a^2/b^2$
5.
Which of these subsets of $\Q$ are Dedekind cuts (non-empty, not all of $\Q$ , closed downwards, no greatest element)? (Choose all that apply.)
- A. $\{q : q < 3\}$
- B. $\{q : q \le 3\}$
- C. $\{q : q^2 < 2\}$
- D. $\{q : q^3 < 2\}$
- E. $\varnothing$
6.
Which example shows that $\Q$ is not complete (that not every non-empty, bounded-above subset has a least upper bound in $\Q$ )?
- A. $\{q \in \Q : q^2 < 2\}$
- B. $\N \subseteq \Q$
- C. $\{q \in \Q : q < 1\}$
- D.the sequence $(-1)^n$
7.
In the lesson's Lean file, PairInt.add is defined with Quotient.map₂ (fun p q => (p.1 + q.1, p.2 + q.2)) (proof). What is the second argument, and what happens if you leave it out?
- A.A proof that equivalent inputs give equivalent outputs (here built from add_respects); without it the definition does not type-check
- B.A proof of commutativity of addition; without it Lean assumes addition is not commutative
- C.An optional hint for the simplifier; leaving it out only makes proofs slower
- D.The decidability of the relation; without it Lean cannot compute
8.
Implement the integers as pairs of natural numbers. Write canonical(p), returning the representative of the class of p that has a $0$ in at least one coordinate, and mul(p, q) using $(a, b)(c, d) = (ac + bd, ad + bc)$ . Then check, for all pairs with entries up to $5$ , that mul is well defined: equivalent inputs give outputs with the same canonical form.
Computational — Practice

Answer key — Constructing ℤ, ℚ and ℝ

1.
The class of $-2$ is $\{(a, a + 2) : a \in \N\} = \{(0, 2), (1, 3), (2, 4), (3, 5), \dots\}$ . So $(0, 2)$ , $(3, 5)$ and $(10, 12)$ belong to it; $(5, 3)$ and $(2, 0)$ represent $+2$ .
2.
$(3 \cdot 4 + 5 \cdot 1,\ 3 \cdot 1 + 5 \cdot 4) = (17, 23)$ , which represents $17 - 23 = -6$ . As expected, $(3, 5)$ represents $-2$ , $(4, 1)$ represents $3$ , and $(-2) \cdot 3 = -6$ — the formula was designed from $(a - b)(c - d) = (ac + bd) - (ad + bc)$ .
3.
Only the final cancellation of $d$ needs it: $(af - eb)d = 0$ and $d \neq 0$ give $af = eb$ precisely because the ring has no zero divisors. In $\Z/6\Z$ , $3/1 \sim 0/2 \sim 0/1$ but $3/1 \not\sim 0/1$ .
4.
The mediant and $a/b \mapsto a + b$ are not well defined (counterexamples above). Ordinary addition, inversion and squaring are: each respects $ab' = a'b$ . A single pair of representatives giving different answers is enough to show a rule is not well defined; a proof is needed to show that one is.
5.
$\{q < 3\}$ and $\{q^3 < 2\}$ are cuts. $\{q \le 3\}$ has a greatest element, $\{q^2 < 2\}$ is not closed downwards (the correct cut is $\{q : q < 0 \text{ or } q^2 < 2\}$ ), and $\varnothing$ is empty.
6.
$\{q : q^2 < 2\}$ is bounded above but has no least upper bound in $\Q$ : for any rational upper bound $r$ (necessarily $r^2 > 2$ ), the rational $\frac{2r + 2}{r + 2}$ is a smaller upper bound. In $\R$ its supremum is $\sqrt 2$ .
7.
The second argument is a proof that the function on pairs respects the equivalence relation — here fun _ _ h₁ _ _ h₂ => add_respects h₁ h₂. Lean's Quotient.map₂ will not produce a function on classes without it, so the well-definedness proof of Proposition 2 is part of the definition itself.
8.
```
def canonical(p):
    m = min(p)
    return (p[0] - m, p[1] - m)

def mul(p, q):
    a, b = p
    c, d = q
    return (a * c + b * d, a * d + b * c)
```
Subtracting $m$ from both coordinates keeps $a + d = c + b$ true, so the canonical form lies in the same class, and it is the only representative with a zero coordinate. The final loop is exhaustive evidence for small pairs; the lesson's Proposition 2 proves well-definedness for all pairs.