Relations: Equivalence and Order

This 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 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}$ .

Two methods of proof are new. Section 4.1 decides a property of a relation by a proof for all elements or by one witness against it, and records the verdicts in a table. Section 4.2 checks that a definition made through a representative does not depend on the representative: the check called well-definedness, promised in Section 1.5. Section 4.3 uses the methods of Chapters 1 and 2 without new scaffolding.

What you need. Logic and Proof, Chapters 1–8, and Sets and Functions, Chapters 1–3. From Logic and Proof: the rules for “there exists” (Logic and Proof, Definition 5.6.1), equality (Logic and Proof, Definition 5.7.1, Logic and Proof, Proposition 5.7.1), negating bounded quantifiers and implications (Logic and Proof, Proposition 6.2.3, Logic and Proof, Proposition 6.2.2), De Morgan and double negation (Logic and Proof, Proposition 2.5.5, Logic and Proof, Proposition 2.5.1), the catalogue of what a proof may not do (Logic and Proof, Example (What is not allowed)), squares and order (Logic and Proof, Theorem 2.4.5), and induction (Logic and Proof, Axiom 4.2.1). From Chapter 1: subsets, set equality and sets cut out by a property (Definition 1.2.2, Definition 1.2.1, Definition 1.2.3, Proposition 1.2.3, Proposition 1.2.1, Proposition 1.2.2); power sets and unions of families (Definition 1.3.2, Definition 1.3.4); ordered pairs and relations as sets of pairs (Definition 1.4.1, Definition 1.4.3); functions, their equality, and rules that are not functions (Definition 1.5.1, Proposition 1.5.1, Example (Relations that are not functions)); surjections and two-sided inverses (Definition 1.5.4, Theorem 1.6.4); preimages (Definition 1.7.2, Proposition 1.7.5); Russell’s theorem (Theorem 1.2.4); divisibility and parity (Definition 1.1.2, Proposition 1.1.1, Theorem 1.1.2); and the methods direct proof, cases, counterexample, double inclusion, uniqueness, injectivity and construct-and-verify (Example (Method: direct proof from a definition), Example (Method: proof by cases), Example (Method: disproof by counterexample, proof by example), Example (Method: two inclusions), Example (Method: existence and uniqueness), Example (Method: proving injectivity), Example (Method: construct and verify)). From Chapter 2: well-ordering and the least-element method (Theorem 2.1.3, Corollary 2.1.5, Example (Method: the least element)); the arithmetic of the integers (Proposition 2.1.2, Lemma 2.1.1); induction from a base (Theorem 2.2.1); the division algorithm and prime factors (Theorem 2.2.3, Theorem 2.2.5); powers (Definition 2.3.2, Proposition 2.3.4); finite maxima (Proposition 2.3.8); choosing between direct proof, contrapositive and contradiction (Example (Method: choosing direct, contrapositive or contradiction)); equinumerous, finite and infinite sets (Definition 2.5.1, Proposition 2.5.1, Corollary 2.5.4, Definition 2.5.2, Definition 2.5.3, Proposition 2.5.6, Example (Hilbert’s Hotel)). From Chapter 3: images of countable sets and the countability of $\mathbb{Z}$ (Proposition 3.1.4, Theorem 3.1.8), for one review exercise, and the axiom of choice (Axiom 3.2.1), for one remark. The arithmetic and order of $\mathbb{R}$ are school facts, as before.

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

Roadmap

Properties of relations. Reflexive, symmetric, antisymmetric and transitive; deciding each one by a proof for all elements or by a single witness, with the verdicts collected in a table of eight relations; divisibility as the relation whose antisymmetry depends on the set.
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 (a correspondence proved in both directions), the integers modulo $n$ , sizes of subsets as a last example, and the method for checking that a definition on classes is well defined.
Partial orders, maximal and greatest elements. Relations that behave like $\le$ , greatest elements against maximal ones and when the two agree, uniqueness from antisymmetry, least upper bounds in a partially ordered set, and well-ordered sets.

Named moves

The first two are method boxes; Chapters 1–3’s boxes are cited where they are used.

Prove or disprove each property (Example (Method: proving or disproving a property of a relation)). A property that holds is a “for all”: take arbitrary related elements and unwind. A property that fails needs one witness: an element, a pair or a triple. (Section 4.1)
Well-definedness (Example (Method: checking that a definition on classes is well defined)). For a rule that reads a representative, take two representatives of one class and show that the outputs agree. (Section 4.2)
Classes from a relation, a relation from classes. Pass between an equivalence relation and its partition, whichever description makes the next step easier.
Uniqueness by antisymmetry. Two candidates, each below the other, are equal: the method of Example (Method: existence and uniqueness) with (PO2) closing the gap. (Section 4.3)

Threads

Same size. The bijections of Section 1.6 say when two sets have the same size; Section 2.5 makes this a definition (Definition 2.5.1); Section 4.2 meets it as an equivalence relation on the subsets of one set (Example (Same size, revisited)), and explains why it is not one on all sets.
The clock. The arithmetic of $\mathbb{Z}/n$ in Section 4.2 returns in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Section 3.4, where $\mathbb{Z}/n$ becomes a ring.
Maximal elements and chains. Section 4.3 ends by asking when a partially ordered set must have a maximal element; Chapter 6 answers with Zorn’s lemma.

Summary

A relation on a set may be reflexive, symmetric, antisymmetric or transitive (Definition 4.1.1); each property is proved for all elements or refuted by one witness. The relations with the first, second and fourth are the equivalence relations (Definition 4.2.1); their classes partition the set (Theorem 4.2.1), and every partition comes from exactly one of them (Theorem 4.2.2). Congruence modulo $n$ gives $\mathbb{Z}/n = \{[0], \dots, [n - 1]\}$ (Proposition 4.2.4), whose sum and product are well defined (Proposition 4.2.5), while some rules on classes are not functions at all (Example (A rule on classes that is not a function)). The relations with the first, third and fourth are the partial orders (Definition 4.3.1). A greatest element is unique (Proposition 4.3.1) and maximal, and the converse needs totality (Proposition 4.3.2); a supremum is the least upper bound (Definition 4.3.5), and under divisibility it is the least common multiple (Example (The supremum under divisibility is the least common multiple)).

What is open: in a partially ordered set where every chain has an upper bound, must there be a maximal element? Nothing proved so far decides it. Chapter 6 states the principle that does, Zorn’s lemma, and puts it to work. Next, Chapter 5 uses quotient sets and well-definedness to build functions: every function factors through the quotient by “same value”.

Terms

antisymmetric: $x \mathrel{R} y$ and $y \mathrel{R} x$ give $x = y$ (Definition 4.1.1).
block: one of the sets of a partition (Definition 4.2.3).
bounded: bounded above and below, that is, with an upper and a lower bound (Definition 4.3.2).
comparable: $x \preceq y$ or $y \preceq x$ (Definition 4.3.1).
congruent modulo $n$ : $a \equiv b \pmod{n}$ , that is, $n \mid a - b$ (Definition 4.2.5).
equivalence class: $[a] = \{ x \in X : x \sim a \}$ (Definition 4.2.2).
equivalence relation: reflexive, symmetric and transitive (Definition 4.2.1).
greatest element: an element of $A$ above every element of $A$ (Definition 4.3.3).
infimum: a greatest lower bound (Definition 4.3.5).
least element: an element of $A$ below every element of $A$ (Definition 4.3.3).
lower bound: an element of $X$ below every element of $A$ (Definition 4.3.2).
maximal element: an element of $A$ with nothing in $A$ strictly above it (Definition 4.3.4).
minimal element: an element of $A$ with nothing in $A$ strictly below it (Definition 4.3.4).
partially ordered set: a set with a reflexive, antisymmetric and transitive relation (Definition 4.3.1).
partition: a set of non-empty, pairwise disjoint subsets whose union is the whole set (Definition 4.2.3).
quotient map: $x \mapsto [x]$ , from $X$ onto $X/{\sim}$ (Definition 4.2.4).
quotient set: the set $X/{\sim}$ of all equivalence classes (Definition 4.2.4).
reflexive: $x \mathrel{R} x$ for every $x \in X$ (Definition 4.1.1).
representative: an element of a class, which names the class (Definition 4.2.2).
strict part: $x \prec y$ , that is, $x \preceq y$ and $x \ne y$ (Definition 4.3.1).
supremum: a least upper bound (Definition 4.3.5).
symmetric: $x \mathrel{R} y$ gives $y \mathrel{R} x$ (Definition 4.1.1).
total: every two elements are comparable (Definition 4.3.1).
transitive: $x \mathrel{R} y$ and $y \mathrel{R} z$ give $x \mathrel{R} z$ (Definition 4.1.1).
upper bound: an element of $X$ above every element of $A$ (Definition 4.3.2).
well defined: a rule on classes whose output does not depend on the representative (Example (Method: checking that a definition on classes is well defined)).
well-ordered set: a partially ordered set whose order is total and in which every non-empty subset has a least element (Definition 4.3.6).