Building the Integers and the Rationals from Equivalence Classes

“Subtract $5$ from $3$” has no answer in $\mathbb{N}$, and “halve $1$” has none among the integers. School answers by inventing $-2$ and $\frac{1}{2}$. This chapter builds them, from pairs and nothing else. The pairs $(3,5)$ and $(0,2)$ both record “two less than nothing”, and the integer $-2$ is the set of all pairs that record it; the pairs $(1,2)$ and $(2,4)$ both record “one divided by two”, and the rational $\frac{1}{2}$ is the set of all pairs that record that. The tool is the quotient of a set by an equivalence relation, from Sets, Relations, and Cardinality, Section 2.5, used twice: once on $\mathbb{N}\times \mathbb{N}$ to make $\mathbb{Z}$, once on $\mathbb{Z}\times {\mathbb{Z}}_{>0}$ to make $\mathbb{Q}$. The one thing that can go wrong is an operation that depends on which pair was used to name a class, and the chapter’s central skill is checking that it does not. At the end, $\mathbb{Q}$ is an ordered field, every rule for inequalities used in this chapter is proved from the order axioms, and every rational lies below a natural number. Yet $\mathbb{Q}$ still has a hole where $\sqrt{2}$ should be: no rational squares to $2$, and the rationals whose square is below $2$ have no least upper bound in $\mathbb{Q}$. Later chapters of this volume fill the hole.

The school picture. Logic and Proof, Chapters 1–8, and Sets, Relations, and Cardinality, Chapters 1–3 treated $\mathbb{Z}$ and $\mathbb{Q}$ as known subsets of the familiar real line (Sets, Relations, and Cardinality, Section 2.1), and used their arithmetic and order as school facts. From this chapter on they are the sets built here, and the familiar facts are theorems. Section 2.2 proves $\mathbb{Z}=\mathbb{N}\cup \{-n:n\in \mathbb{N}\}$, the description that Sets, Relations, and Cardinality, Section 2.1 took as a definition, and Section 2.4 proves $\mathbb{Q}=\{m/n:m\in \mathbb{Z},n\in {\mathbb{Z}}_{>0}\}$ in the same way. Nothing earlier was circular: Logic and Proof, Chapters 1–8, and Sets, Relations, and Cardinality, Chapters 1–3 used these facts as stated facts, never as proved ones. No proof in this chapter uses a school fact about the integers, the rationals or the real numbers; school decimals appear once, in a table in Section 2.6 marked as being for orientation only. The results of Sets, Relations, and Cardinality, Chapters 2 and 3 about their integers, such as the division algorithm and congruences, are not cited for the constructed $\mathbb{Z}$; a later chapter of this volume rebuilds them.

What you need. Chapter 1 and Sets, Relations, and Cardinality, Chapters 1 and 2, chiefly Chapter 1 and Sets, Relations, and Cardinality, Section 2.5. From Chapter 1, the natural numbers $\omega$ with the citing rule of Section 1.7 (Corollary 1.7.3), by which $\mathbb{N}$ means $\omega$ and induction (Logic and Proof, Axiom 4.2.1) and the recursion theorem (Sets, Relations, and Cardinality, Theorem 2.3.1) of Logic and Proof, Chapter 4, and Sets, Relations, and Cardinality, Chapter 2 apply to it; the arithmetic of $\omega$ (Definition 1.5.1, Theorem 1.5.3, Corollary 1.5.2), its order, cancellation and subtraction (Theorem 1.6.1, Proposition 1.6.3), well-ordering (Theorem 1.6.2), induction and recursion on $\omega$ (Theorem 1.3.3, Theorem 1.5.1), and the theorem that no pair is a natural number (Proposition 1.4.3). From Sets, Relations, and Cardinality, Section 2.5: equivalence relations, classes and quotient sets (Sets, Relations, and Cardinality, Definition 2.5.1, Sets, Relations, and Cardinality, Definition 2.5.2, Sets, Relations, and Cardinality, Definition 2.5.4, Sets, Relations, and Cardinality, Theorem 2.5.1), and the two examples that this chapter generalizes, arithmetic modulo $n$ (Sets, Relations, and Cardinality, Proposition 2.5.5) and a rule on classes that is not a function (Sets, Relations, and Cardinality, Example (A rule on classes that is not a function)). From Sets, Relations, and Cardinality, Section 2.6: partial orders, upper bounds and suprema (Sets, Relations, and Cardinality, Definition 2.6.1, Sets, Relations, and Cardinality, Definition 2.6.2, Sets, Relations, and Cardinality, Definition 2.6.5). From Sets, Relations, and Cardinality, Chapter 1: sets cut out by a property (Sets, Relations, and Cardinality, Definition 1.1.3), ordered pairs, products and relations (Sets, Relations, and Cardinality, Definition 1.3.1, Sets, Relations, and Cardinality, Definition 1.3.2, Sets, Relations, and Cardinality, Definition 1.3.3), and functions, their equality and injectivity (Sets, Relations, and Cardinality, Definition 1.4.1, Sets, Relations, and Cardinality, Proposition 1.4.1, Sets, Relations, and Cardinality, Definition 1.4.3). From Logic and Proof, Chapter 8, the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)), for the find-the-error exercises. Section 2.6 compares its proof with Logic and Proof, Chapter 2’s parity proof that $\sqrt{2}$ is irrational (Logic and Proof, Theorem 2.2.1), which it does not use, and names the rule $\mathrm{\neg }\mathrm{I}$ (Logic and Proof, Definition 2.2.1, Logic and Proof, Definition 2.5.1). A few exercises reach further back: the negation laws of Logic and Proof, Chapters 2 and 6 (Logic and Proof, Proposition 2.5.5, Logic and Proof, Proposition 6.2.1, Logic and Proof, Proposition 6.2.3, Logic and Proof, Proposition 6.2.2) in Section 2.5’s A1 and in review exercise R3; finite and infinite sets (Sets, Relations, and Cardinality, Definition 3.1.2, Sets, Relations, and Cardinality, Definition 3.1.3, Sets, Relations, and Cardinality, Corollary 3.1.3, Sets, Relations, and Cardinality, Proposition 3.1.6) in Section 2.3’s C1; a quotient by the fibers of a function (Sets, Relations, and Cardinality, Example (The fibers of a function)) in Section 2.2’s C1; and countable sets (Sets, Relations, and Cardinality, Theorem 3.2.6, Sets, Relations, and Cardinality, Corollary 3.2.7, Sets, Relations, and Cardinality, Proposition 3.2.3, Sets, Relations, and Cardinality, Proposition 3.2.4) in review exercise R2, read on $\omega$ through Section 1.7 (Proposition 1.6.4).

Time. About 25 hours on the core track (all of A, one B and one C per section, the exit checks); about 35 hours for everything.

Roadmap

• The Integers as Classes of Pairs. Pairs $(a,b)$ of natural numbers as notes saying “$a$ minus $b$”, the cross-sum relation $a+d=b+c$ proved an equivalence relation by cancellation in $\mathbb{N}$, $\mathbb{Z}$ as its quotient set, the classes drawn as diagonals of the quarter plane, and the normal form $[(n,0)]$ or $[(0,n)]$ of each integer.
• Well-Definedness, and the Arithmetic of the Integers. The lemma that a rule on classes is a function as soon as equivalent inputs give equivalent outputs (for maps, for binary operations one argument at a time, and for properties), the sum, product and negative of integers checked against it, rules that fail it, and the copy of $\mathbb{N}$ inside $\mathbb{Z}$ that makes $\mathbb{Z}=\mathbb{N}\cup \{-n:n\in \mathbb{N}\}$ a theorem.
• The Integers as an Ordered Ring. The axioms (F1)–(F9) of a commutative ring and of a field, $\mathbb{Z}$ a commutative ring by reduction of each law to $\mathbb{N}$, ordered rings and the orders that come from a positive set, the order of $\mathbb{Z}$ and its discreteness, the rules for inequalities in every ordered ring, least elements of bounded sets of integers, and a field with two elements that cannot be ordered.
• The Rationals as Classes of Fractions. Pairs $(p,q)$ with $q>0$ identified by cross-multiplication, $\mathbb{Q}$ as their quotient set with a well-defined sum and product, the proof that $\mathbb{Q}$ is a field, the copy of $\mathbb{Z}$ inside it that turns the class $[(p,q)]$ into the quotient $p/q$, and why non-zero denominators would give the same set but spoil the order.
• The Rationals as an Ordered Field; the Archimedean Property. The positive rationals as the classes with a positive numerator, $\mathbb{Q}$ an ordered field with the comparison formula $p/q<r/s⟺ps<rq$, reciprocals reversing order, a midpoint between any two rationals, the Archimedean property proved from the construction with no supremum in sight, its form $1/n<\epsilon$ for rational $\epsilon >0$, and the integer part $\lfloor x\rfloor$.
• The Gaps in the Rationals. No rational squares to $2$, proved by descent on a least denominator rather than by parity, the set $\{x\in \mathbb{Q}:x^2<2\}$ bounded above with no supremum in $\mathbb{Q}$, and the rational sequence $2,\frac{3}{2},\frac{17}{12},\frac{577}{408},\dots$ that closes in on the gap from above; the review exercises reach back to Chapter 1, Logic and Proof, Chapters 2, 6, and Sets, Relations, and Cardinality, Chapters 2, 3.

Named moves

• Check on representatives, one argument at a time. To show that $[x]\ast [y]:=[g(x,y)]$ is well defined, change $x$ to an equivalent $x^{\prime }$ with $y$ fixed, then $y$ to an equivalent $y^{\prime }$ with $x^{\prime }$ fixed, and join the two changes by transitivity, as the lemma of Section 2.2 does. Each change is one computation at the level below. When the formula is symmetric in its two inputs, the second change comes free. A formula that merely looks right is not yet a definition.
• Reduce to the level below. A law about classes, written on representatives, becomes an identity in $\mathbb{N}$ (for $\mathbb{Z}$) or in $\mathbb{Z}$ (for $\mathbb{Q}$), which is already proved. The two sides are either the same pair or two related pairs, and in both cases the classes agree.
• Order from a positive set. To order a commutative ring, say which elements are positive, check that they are closed under $+$ and $\cdot$ and that every element is exactly one of positive, zero or minus a positive, and let $a<b$ mean that $b-a$ is positive. Every rule for inequalities then follows by turning the comparison into one positive element.