Equivalence Relations, Orders, and Induction

Logic and Proof, Chapter 4 took one fact about the natural numbers on trust: induction. Everything else we have used about them came from school: that $7-3$ is a natural number, that none lies strictly between $3$ and $4$, that every non-empty set of them has a least member, that every integer is even or odd and not both. This chapter derives all of these from induction, extends them to the integers, and proves that the least-member property, well-ordering, is induction in another form. It then turns induction from a principle into a craft: which form fits a claim, where to start, when to argue from a smallest counterexample, when to prove more than was asked, and how a flawed induction fails at exactly one step. It also proves that a starting value and a rule for the next value really do define a sequence, which is what makes $\sum$, $\prod$, $n!$ and powers definitions rather than abbreviations. The first motivating problem comes from Logic and Proof, Chapter 2, which reduced a fraction by halving numerator and denominator for as long as both were even: what stops the halving from going on for ever?

The second half of the chapter is about relations. When is “the same” a legitimate way to identify different things, as a clock identifies $2$ with $14$, or a function identifies two points with the same value? And what does “larger” mean when not everything can be compared, as with sets under inclusion or natural numbers under divisibility? The second motivating problem: in what sense is “$9+5=2$ on a clock” a true statement? The answer is an equivalence relation, the partition it cuts its set into, and a check that arithmetic on the pieces does not depend on which integer names a piece. For orders the answer is that “largest” splits into two notions, greatest and maximal, which agree only when every two elements are comparable. The last section reaches least upper bounds in a general partially ordered set (Analysis on the Real Line, Chapter 1’s supremum is the case of $\le$ on $\mathbb{R}$, and its axiom says that such suprema exist) and closes with well-ordered sets, the order-theoretic name for what Section 2.1 proved about $\mathbb{N}$.

What you need. Logic and Proof, Chapters 1–8, and Sets, Relations, and Cardinality, Chapter 1. From Logic and Proof, Chapters 1 and 2: the $\to \mathrm{I}$ box (Logic and Proof, Definition 1.4.1), proof by contradiction (Logic and Proof, Definition 2.5.1), and the two results whose school facts this chapter proves, the irrationality of $\sqrt{2}$ (Logic and Proof, Theorem 2.2.1) and Logic and Proof, Theorem 2.1.3. From Logic and Proof, Chapter 4: the principle of induction (Logic and Proof, Axiom 4.2.1) and strong induction (Logic and Proof, Theorem 4.2.2), with the worked examples that introduced them (Logic and Proof, Example (A sum of products of neighbors), Logic and Proof, Example (An inequality by induction), Logic and Proof, Example (Threes and fives)), and structural recursion and induction (Logic and Proof, Theorem 4.3.4, Logic and Proof, Theorem 4.3.1), which appear here as pointers back and in one review exercise. From Logic and Proof, Chapters 5 and 6: the rules for “for every” and “there exists” (Logic and Proof, Definition 5.4.1, Logic and Proof, Definition 5.6.1), the rules for equality (Logic and Proof, Definition 5.7.1, Logic and Proof, Proposition 5.7.1), bounded quantifiers (Logic and Proof, Proposition 6.1.1), and negating quantifiers and implications (Logic and Proof, Proposition 6.2.3, Logic and Proof, Proposition 6.2.2). From Logic and Proof, Chapter 8: how an induction is written in prose (Logic and Proof, Example (An induction, and a legitimate symmetry)) and the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)). From Chapter 1: sets cut out by a property (Definition 1.1.3), power sets (Definition 1.2.2), unions of families (Definition 1.2.4), relations as sets of pairs (Definition 1.3.3), functions and when two are equal (Definition 1.4.1, Proposition 1.4.1), and preimages (Definition 1.6.2). The arithmetic and order of $\mathbb{R}$ are school facts, as in the earlier chapters; Analysis on the Real Line, Chapter 1 states them as axioms.

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

Roadmap

• The natural numbers and well-ordering. From induction alone, the arithmetic of $\mathbb{N}$ and $\mathbb{Z}$, the proof that every non-empty set of natural numbers has a least element, and the theorem that induction and well-ordering are equivalent, with a witness for each hypothesis it needs.
• Induction, strong induction and the smallest counterexample. Induction and strong induction from any integer, the smallest counterexample as a method, the division algorithm, lowest terms and prime factors as its first uses, and the ways an induction proof goes wrong, each located at one step.
• Definition by recursion. The theorem that a starting value and a rule define exactly one sequence, its variants from another base and with two previous values, sums, products and powers defined by it, and inductions that follow a definition’s clauses or prove more than was asked.
• Properties of relations. Reflexive, symmetric, antisymmetric and transitive, each failure proved by a witness, divisibility as the relation whose antisymmetry depends on the set, and a table of eight relations checked against the four properties.
• Equivalence relations and partitions. Relations that behave like equality, the proof that their classes partition the set and that every partition arises from exactly one of them, the integers modulo $n$, and why arithmetic on classes must be checked to be well defined.
• Partial orders, maximal and greatest elements. Relations that behave like $\le$, greatest elements against maximal ones and when the two agree, least upper bounds in a partially ordered set, and well-ordered sets.

Named moves

• Smallest counterexample. Suppose the claim fails; well-ordering gives a least failure $m$; below $m$ the claim holds, and from that produce a failure smaller than $m$, or the claim at $m$ itself.
• Prove more (strengthen the hypothesis). When the inductive step will not go through, ask what the induction hypothesis would need to say, and prove that stronger statement instead.
• Recursion, then induction. Define an object by a recursion, and prove facts about it by an induction that follows the same clauses: the base case uses the starting value, and the step uses the rule.
• Classes from a relation, a relation from classes. Pass between an equivalence relation and its partition, whichever description makes the next step easier.