← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 6

Relations and Order

Taught 16 Aug 2026

Relations and Order

People classify: we decide which things belong together, and mathematics does this on every page. This chapter covers relations in general, then the two most important kinds, orders and equivalences, and finally the way an equivalence cuts a set into pieces.

Relations

A relation records, for each pair of elements, whether the two stand in a given relationship. Since a pair with an order to it is an ordered pair, and the set of all of them is a Cartesian product, no new definitions are needed.

Definition 6.1 (Binary relation).

A relation $R$ on a set $S$ is a set of ordered pairs of elements of $S$ , that is, a subset $R \subset S \times S$ . We abbreviate $(x, y) \in R$ to $x \mathbin{R} y$ , and say $x$ is related to $y$ by $R$ ; if $(x, y) \notin R$ we write $x \not\mathbin{R} y$ .

Putting the symbol between the two elements is infix notation; writing $R(x, y)$ instead is prefix notation. For equivalence relations we usually take a symbol such as $\equiv$ or $\sim$ , and for strict orders the symbol $<$ .

Two relations are distinguished exactly by the pairs belonging to one and not the other, since a relation is its set of pairs. At the two extremes, $S \times S$ is the universal relation on $S$ and $\emptyset$ is the empty relation. Neither is of much interest: if everything is related to everything then being related is no mark of distinction, and if nothing is related to anything there is nothing to say.

Definition 6.2 (Reflexive, symmetric, transitive).

Let $R$ be a relation on a set $S$ . Then $R$ is

reflexive if $x \mathbin{R} x$ for every $x \in S$ ;
symmetric if $x \mathbin{R} y \implies y \mathbin{R} x$ for all $x, y \in S$ ;
transitive if $(x \mathbin{R} y \land y \mathbin{R} z) \implies x \mathbin{R} z$ for all $x, y, z \in S$ .

Example 6.3.

From a familiar children’s game, let $S = \{\text{rock}, \text{scissors}, \text{paper}\}$ and let $B$ , read “beats”, be

B = \bigl\{(\text{rock}, \text{scissors}), (\text{scissors}, \text{paper}), (\text{paper}, \text{rock})\bigr\}.

This $B$ is none of the three: rock does not beat itself, rock beats scissors while scissors does not beat rock, and rock beats scissors and scissors beats paper while rock does not beat paper.

Definition 6.4 (Equivalence relation).

A relation is an equivalence relation if it is reflexive, symmetric and transitive. When $\sim$ is an equivalence relation and $x \sim y$ , we say $x$ and $y$ are equivalent with respect to $\sim$ .

Example 6.5.

On $S = \{1, 2, 3, 4\}$ the relation $R = \{(1,2), (2,1), (1,1), (2,2)\}$ is symmetric and transitive but not reflexive, since $3 \not\mathbin{R} 3$ . Adjoining exactly what is missing gives $R_1 \defeq R \cup \{(3,3), (4,4)\}$ , which is reflexive, inherits symmetry and transitivity, and is therefore an equivalence relation. We call $R_1$ the reflexive closure of $R$ : it adds to $R$ only the pairs that reflexivity requires.

Example 6.6.

Transitivity is the condition that most often fails. Let $S$ be the partially exposed stones in a stream you wish to cross, and for $x, y \in S$ let $x \sim y$ mean that you can step directly from $x$ to $y$ without getting wet. This is reflexive, since once on a stone you can hop on the spot, and symmetric, since a step you can take one way you can take back. It is not generally transitive: that you can reach $y$ from $x$ and $z$ from $y$ says nothing about reaching $z$ from $x$ in one step.

Problem 6.1.

Check that the relation $R = \{(1,2), (2,1), (1,1), (2,2)\}$ above is symmetric and transitive, working from the definitions rather than from the picture.

Problem 6.2.

Let $A$ and $B$ be sets. Many texts call a subset $R \subset A \times B$ a relation from $A$ to $B$ . Show that every such $R$ is a relation on $A \cup B$ in the sense of Definition 6.1 .

Problem 6.3.

Let $R$ be a symmetric and transitive relation on a set $S$ , and put $T \defeq \{x \in S \mid x \mathbin{R} x\}$ . Show that $x \mathbin{R} y$ implies $x, y \in T$ , and that $R$ is an equivalence relation on $T$ .

Order Relations

Orders are the second of the two kinds of relation we shall need. We isolate the properties an order has, so that when we later build one on the natural numbers out of addition alone we know exactly what has to be checked.

Definition 6.7 (Strict linear order).

A strict linear order on a set $S$ is a relation, commonly written $<$ , satisfying

the transitivity law: for all $x, y, z \in S$ , if $x < y$ and $y < z$ then $x < z$ ;
the trichotomy law: for all $x, y \in S$ , exactly one of $x < y$ , $x = y$ , $y < x$ holds.

When $x < y$ holds we say $x$ is strictly less than $y$ . Strict linear orders are also called strict total orders, in contrast with the partial orders of the next section. The word exactly in the trichotomy law says two things: any two elements can be compared, and no two of the alternatives hold at once. Proofs use the second far more often than the first, so we isolate it.

Proposition 6.8 (Anti-reflexivity).

Let $<$ be a strict linear order on a set $S$ . Then $\neg(x < x)$ for every $x \in S$ .

Discussion.

The statement is a universally quantified negation, so we fix an arbitrary $x$ and rule out $x < x$ . Only the trichotomy law says anything about a single pair, so we apply it to the pair $x$ and $x$ . It offers three alternatives, $x < x$ , $x = x$ and $x < x$ , and exactly one of them holds. The middle one holds, since equality is reflexive, which rules out the other two; and each of those is the statement we wish to deny.

Proof.

Let $x \in S$ . Trichotomy applied to $x$ and $x$ says that exactly one of $x < x$ , $x = x$ , $x < x$ holds. Since $x = x$ holds, neither occurrence of $x < x$ can, so $\neg(x < x)$ .

Trichotomy can be traded for the weaker demand that at least one alternative hold, provided we also assume anti-reflexivity.

Proposition 6.9 (Characterising strict linear orders).

Let $<$ be a relation on a set $S$ such that

for all $x, y, z \in S$ , if $x < y$ and $y < z$ then $x < z$ ;
for all $x, y \in S$ , $(x < y) \lor (x = y) \lor (y < x)$ ;
for all $x \in S$ , $\neg(x < x)$ .

Then $<$ is a strict linear order on $S$ .

Discussion.

The definition asks for two laws, and the first is the first hypothesis verbatim, so only trichotomy needs proof. It splits in two: that at least one alternative holds is the second hypothesis, again verbatim, and it remains to show that no two hold together. There are three possible pairs, the two strict comparisons together or either strict comparison alongside $x = y$ , and we take them in turn. Two opposite strict comparisons feed into transitivity and produce $x < x$ ; a strict comparison alongside an equality lets us substitute one letter for the other and produce $x < x$ again. Each case gives $x < x$ , which the third hypothesis forbids.

Proof.

The first hypothesis is the transitivity law. For trichotomy, let $x, y \in S$ . The second hypothesis gives at least one of $x < y$ , $x = y$ , $y < x$ .

If both $x < y$ and $y < x$ held, transitivity would give $x < x$ , against the third hypothesis. If $x < y$ and $x = y$ held, substitution gives $x < x$ ; and $y < x$ with $x = y$ gives $x < x$ likewise. So no two of the alternatives hold together, exactly one holds, and that is the trichotomy law.

A strict order says which of two elements comes first. For bounds, minima and induction it is more convenient to use the relation that also allows equality.

Definition 6.10 (Associated non-strict order).

Let $<$ be a strict linear order on a set $S$ . The associated non-strict order $\leqslant$ is defined by: $x \leqslant y$ holds if and only if $(x < y) \lor (x = y)$ holds. When $x \leqslant y$ we say $x$ is less than or equal to $y$ .

Proposition 6.11 (Laws of the associated order).

Let $<$ be a strict linear order on $S$ with associated $\leqslant$ . For all $x, y \in S$ :

$(x \leqslant y) \lor (y \leqslant x)$ ;
if $x \leqslant y$ and $y \leqslant x$ then $x = y$ ;
$\neg(x \leqslant y)$ if and only if $y < x$ ;
$\neg(x < y)$ if and only if $y \leqslant x$ .

Discussion.

All four come from the list of three alternatives in trichotomy, so in each we go through the list and see which entries remain. The first is a disjunction and every entry produces one of its halves: $x < y$ gives $x \leqslant y$ , $y < x$ gives $y \leqslant x$ , and $x = y$ gives both. The second is a conditional whose conclusion is an equality, so we suppose $x \neq y$ and derive a contradiction: the definition turns both hypotheses into strict comparisons, transitivity gives $x < x$ , and anti-reflexivity forbids it. The last two are biconditionals, proved by crossing entries off the list. Denying $x \leqslant y$ deletes the first two entries and leaves $y < x$ ; conversely $y < x$ deletes those same two, since trichotomy allows only one. Denying $x < y$ deletes just the first entry, leaving $x = y$ or $y < x$ , and that pair is what $y \leqslant x$ abbreviates.

Proof.

For the first, trichotomy gives $x < y$ , $x = y$ or $y < x$ , and in each case the definition gives $x \leqslant y$ or $y \leqslant x$ .

For the second, suppose $x \leqslant y$ and $y \leqslant x$ , and suppose $x \neq y$ . Then the definition gives $x < y$ and $y < x$ , so transitivity gives $x < x$ , contradicting anti-reflexivity. Hence $x = y$ .

For the third, if $\neg(x \leqslant y)$ then neither $x < y$ nor $x = y$ holds, so trichotomy leaves $y < x$ . Conversely $y < x$ excludes both $x < y$ and $x = y$ , so $\neg(x \leqslant y)$ .

For the fourth, trichotomy says $\neg(x < y)$ holds precisely when $x = y$ or $y < x$ , which by the definition is precisely $y \leqslant x$ .

From transitivity of $<$ we get two further transitivity laws, one for each way of mixing the two relations.

Proposition 6.12 (Mixed transitivity).

Let $<$ be a strict linear order on $S$ with associated $\leqslant$ , and let $x, y, z \in S$ . Then

if $x < y$ and $y \leqslant z$ then $x < z$ ;
if $x \leqslant y$ and $y < z$ then $x < z$ .

Discussion.

Each part has one strict hypothesis and one non-strict one, and the definition of $\leqslant$ splits the non-strict hypothesis into two cases, so each part has two cases. In the equality case no order reasoning is needed at all: the conclusion is the strict hypothesis with one letter renamed. In the strict case both hypotheses are strict, so the transitivity law applies.

Proof.

For the first, if $y = z$ then $x < z$ is the hypothesis $x < y$ with $z$ written for $y$ ; and if $y < z$ then transitivity gives $x < z$ .

For the second, if $x = y$ then $x < z$ is the hypothesis $y < z$ with $x$ written for $y$ ; and if $x < y$ then transitivity again gives $x < z$ .

Corollary 6.13 (Transitivity of the non-strict order).

Let $<$ be a strict linear order on $S$ with associated $\leqslant$ . If $x \leqslant y$ and $y \leqslant z$ then $x \leqslant z$ .

Proof.

If $x = y$ and $y = z$ then $x = z$ . If $x = y$ and $y < z$ then $x < z$ ; if $x < y$ and $y = z$ then $x < z$ ; and if $x < y$ and $y < z$ then mixed transitivity gives $x < z$ . In every case the definition of $\leqslant$ gives $x \leqslant z$ .

Definition 6.14 (Reverse orders).

Let $<$ be a strict linear order on $S$ . We write $x > y$ to mean $y < x$ , and say $x$ is strictly greater than $y$ ; and $x \geqslant y$ to mean $(x > y) \lor (x = y)$ , and say $x$ is greater than or equal to $y$ .

Since $<$ and $\leqslant$ are transitive, so are $>$ and $\geqslant$ .

Definition 6.15 (Chains).

The notation $a < b < c$ abbreviates $(a < b) \land (b < c)$ , and similarly for $>$ , $\leqslant$ and $\geqslant$ , for more than three terms, and for mixtures: $a \leqslant b < c < d$ abbreviates $(a \leqslant b) \land (b < c) \land (c < d)$ .

By transitivity, $a < b < c$ gives $a < c$ .

Problem 6.4.

What is the difference between the trichotomy law and the weak trichotomy law? Which of the two implies the other?

Problem 6.5.

Show that a strict linear order is not symmetric on any set with at least two elements, and decide whether the associated $\leqslant$ can ever be symmetric.

Partial Orders and Extrema

The order relations of the previous section were strict and linear: transitive and trichotomous, with the non-strict $\leqslant$ built afterwards. There is a second tradition, equally common, which takes the non-strict relation as primitive and weakens trichotomy so that incomparable pairs are allowed. That is the language of partial orders, and it is what one wants for inclusion of sets.

Definition 6.16 (Partial order).

A relation $R$ on a set $M$ is a partial order, and $M$ is then ordered by $R$ , if $R$ is

reflexive: $a \mathbin{R} a$ for every $a \in M$ ;
antisymmetric: $a \mathbin{R} b$ and $b \mathbin{R} a$ imply $a = b$ ;
transitive: $a \mathbin{R} b$ and $b \mathbin{R} c$ imply $a \mathbin{R} c$ .

We usually write $a \leqslant b$ for $a \mathbin{R} b$ , and then $a < b$ for $(a \leqslant b) \land (a \neq b)$ , with $b \geqslant a$ and $b > a$ as before.

Definition 6.17 (Comparable elements and total orders).

Let $M$ be partially ordered. Elements $a, b \in M$ are comparable if $a \leqslant b$ or $b \leqslant a$ . The order is a total order, or linear order, if every two elements are comparable.

Example 6.18.

The power set $\mathcal{P}(M)$ is partially ordered by $\subset$ , and also by the reverse inclusion. It is not totally ordered as soon as $M$ has two elements $a$ and $b$ , since $\{a\}$ and $\{b\}$ are incomparable: neither contains the other. The natural numbers will turn out to be totally ordered, once we put an order on them below.

Remark (Partial versus strict).

The two languages agree on total orders. If $<$ is a strict linear order and $\leqslant$ is the associated relation, then $\leqslant$ is a total order in the present sense: reflexivity is immediate, antisymmetry is one of the laws proved above, and transitivity is its corollary. Conversely, from a total order $\leqslant$ the relation $a < b \iff (a \leqslant b) \land (a \neq b)$ is a strict linear order. What partial orders add is the possibility that some pairs are incomparable.

Definition 6.19 (Minimal and maximal elements).

Let $M$ be partially ordered and $A \subset M$ non-empty. An element $a_0 \in A$ is minimal in $A$ if no element of $A$ is strictly smaller, that is, $\{a \in A \mid a < a_0\} = \emptyset$ ; and $a_1 \in A$ is maximal in $A$ if no element of $A$ is strictly larger.

A bound of a set need not lie in the set; a minimum or maximum must.

Definition 6.20 (Bounds, minima, maxima).

Let $S$ be a subset of a partially ordered set $U$ .

An element $b \in U$ is a lower bound of $S$ if $b \leqslant x$ for every $x \in S$ , and $B \in U$ is an upper bound if $x \leqslant B$ for every $x \in S$ .
An element $m \in S$ is a minimum, or least element, of $S$ if $m \leqslant x$ for every $x \in S$ ; and $M \in S$ is a maximum, or greatest element, if $x \leqslant M$ for every $x \in S$ .

The difference is membership: a minimum is a lower bound that happens to lie in $S$ . Not every subset has either, as the natural numbers will shortly illustrate: they have a least element and no greatest one.

Proposition 6.21 (A bound inside the set is an extremum).

Let $S$ be a subset of a partially ordered set. If $b$ is a lower bound of $S$ and $b \in S$ , then $b$ is a minimum of $S$ ; and if $B$ is an upper bound of $S$ with $B \in S$ , then $B$ is a maximum.

Discussion.

The two halves are dual, so it is enough to plan the first and reverse the inequalities for the second. What we are given is a lower bound of $S$ that also lies in $S$ . The bound hypothesis is $b \leqslant x$ for every $x \in S$ , which is the inequality a minimum must satisfy, and the membership is precisely the extra clause the definition of a minimum asks for. Together these are the claim; the two definitions differ only by that clause.

Proof.

If $b$ is a lower bound of $S$ then $b \leqslant x$ for every $x \in S$ , and $b \in S$ by hypothesis; those two together are the definition of a minimum. The argument for maxima is the same with the inequalities reversed.

Existence may fail, but uniqueness does not.

Proposition 6.22 (Uniqueness of extrema).

Let $S$ be a subset of a partially ordered set. The minimum of $S$ , if it exists, is unique, and likewise the maximum.

Discussion.

Suppose two elements are both minima. Each, being a minimum, is below every element of $S$ , and each, being a minimum, lies in $S$ ; so applying the defining property of the first to the second and of the second to the first gives the two inequalities antisymmetry needs. The argument for maxima is identical with the inequalities reversed. The proposition does not say that a minimum exists, only that there cannot be two. Bounds outside $S$ are under no such restriction, since a set may have many lower bounds.

Proof.

Let $m_1$ and $m_2$ both be minima of $S$ . Then $m_1 \leqslant m_2$ , since $m_1$ is a minimum and $m_2 \in S$ ; and $m_2 \leqslant m_1$ for the same reason with the roles exchanged. Antisymmetry gives $m_1 = m_2$ . The argument for maxima is identical.

Problem 6.6.

For $\mathcal{P}(M)$ ordered by inclusion, identify the minimum and the maximum. In $\mathcal{P}(M) \setminus \{\emptyset\}$ , show that every singleton is minimal, and decide whether there is a minimum.

Problem 6.7.

Let $A$ and $B$ be totally ordered sets and let $f : A \to B$ be a bijection with $f(a) < f(b)$ whenever $a < b$ . Show that $a < b$ whenever $f(a) < f(b)$ , and deduce that $f^{-1}$ has the same property.

Partitions

Consider a three-piece jigsaw. How many states of assembly are there, counting two states as different when one has two pieces interlocked that the other does not? The answer is five. Representing each cluster of interlocked pieces by the set of its numbers, each state becomes a family of such sets:

\begin{aligned} \Pi_A &= \bigl\{\{1,2,3\}\bigr\}, & \Pi_B &= \bigl\{\{1,2\}, \{3\}\bigr\}, & \Pi_C &= \bigl\{\{2,3\}, \{1\}\bigr\}, \\ \Pi_D &= \bigl\{\{1,3\}, \{2\}\bigr\}, & \Pi_E &= \bigl\{\{1\}, \{2\}, \{3\}\bigr\}. \end{aligned}

Each is a family of non-empty sets whose union is $\{1,2,3\}$ , no two of which share an element.

Definition 6.23 (Partition).

Let $S$ be a non-empty set. A partition $\Pi$ of $S$ is an indexed family $\Pi \defeq \{A_i\}_{i \in I}$ of non-empty subsets of $S$ with

\bigcup_{i \in I} A_i = S, \qquad A_i \cap A_j = \emptyset \ \text{ whenever } i \neq j.

The $A_i$ are the blocks of the partition.

Example 6.24.

The set $S = \{1,2,3,4\}$ has $\bigl\{\{1,2,3,4\}\bigr\}$ as its only one-block partition, and seven with two blocks:

\begin{aligned} &\bigl\{\{1\}, \{2,3,4\}\bigr\}, \quad \bigl\{\{2\}, \{1,3,4\}\bigr\}, \quad \bigl\{\{3\}, \{1,2,4\}\bigr\}, \quad \bigl\{\{4\}, \{1,2,3\}\bigr\}, \\ &\bigl\{\{1,2\}, \{3,4\}\bigr\}, \quad \bigl\{\{1,3\}, \{2,4\}\bigr\}, \quad \bigl\{\{1,4\}, \{2,3\}\bigr\}. \end{aligned}

It has six with three blocks, and its only four-block partition is $\bigl\{\{1\},\{2\},\{3\},\{4\}\bigr\}$ .

A partition is how we get a handle on a large set: cut it into blocks, deal with the blocks one at a time, and put the pieces back together. The blocks are usually chosen by a shared feature.

Example 6.25 (Informal).

Assuming you know the real numbers, let $S$ be a set of them and suppose a calculation requires that we treat numbers differently according to sign. Take the three blocks

A_1 \defeq \{x \in S \mid x > 0\}, \qquad A_2 \defeq \{x \in S \mid x < 0\}, \qquad A_3 \defeq \{0\}.

This is a partition only if $S$ holds a positive number, a negative number and zero, since blocks are required to be non-empty. Without that requirement every family of conditions would partition every set.

Problem 6.8.

List the six three-block partitions of $\{1,2,3,4\}$ .

Equivalence Classes

Fix an equivalence relation $\sim$ on a set $S$ . We cut $S$ into pieces by grouping together everything related to a given element.

Definition 6.26 (Equivalence class).

Let $\sim$ be an equivalence relation on a set $S$ and let $x \in S$ . The equivalence class of $x$ is

[x] \defeq \{s \in S \mid s \sim x\},

and the set of all equivalence classes is

S/{\sim} \defeq \bigl\{[x] \mid x \in S\bigr\} \subset \mathcal{P}(S),

called $S$ modulo $\sim$ , or the quotient of $S$ by $\sim$ .

Example 6.27.

On $S = \{1,2,3,4\}$ with the equivalence relation $R_1$ above, $[1] = [2] = \{1,2\}$ , $[3] = \{3\}$ and $[4] = \{4\}$ . Distinct classes here do not meet, and the next proposition shows this always happens.

Proposition 6.28 (Characterising equivalence classes).

Let $\sim$ be an equivalence relation on a set $S$ and let $a, b \in S$ . The following are equivalent.

$a \sim b$ ;
$[a] \cap [b] \neq \emptyset$ ;
$[a] = [b]$ .

Discussion.

Three statements would ordinarily need six implications, but a cycle is enough: we prove $1 \implies 3 \implies 2 \implies 1$ and let each statement reach every other by going round. For $1 \implies 3$ we assume $a \sim b$ and aim at an equality of sets, so we chase an element: $c \in [a]$ means $c \sim a$ , and the chain $c \sim a \sim b$ closes by transitivity, with symmetry supplying whichever direction the chain needs; the reverse inclusion is the same argument with $a$ and $b$ exchanged. For $3 \implies 2$ reflexivity puts $a$ in $[a]$ , so if the classes agree then $a$ itself witnesses that they meet. For $2 \implies 1$ a shared element $c$ gives $c \sim a$ and $c \sim b$ , and symmetry with transitivity gives $a \sim b$ . Only the three defining properties are used.

Proof.

$1 \implies 3$ . Suppose $a \sim b$ and let $c \in [a]$ , so $c \sim a$ . With $a \sim b$ transitivity gives $c \sim b$ , that is $c \in [b]$ ; hence $[a] \subset [b]$ . Symmetry gives $b \sim a$ , and the same argument with $a$ and $b$ exchanged gives $[b] \subset [a]$ . So $[a] = [b]$ .

$3 \implies 2$ . Reflexivity gives $a \sim a$ , so $a \in [a]$ . If $[a] = [b]$ then $a \in [a] \cap [b]$ , which is therefore non-empty.

$2 \implies 1$ . Let $c \in [a] \cap [b]$ . Then $c \sim a$ and $c \sim b$ . Symmetry gives $a \sim c$ , and transitivity with $c \sim b$ gives $a \sim b$ .

Remark (Disjoint decomposition).

It follows that $S$ is the union of the classes and that distinct classes are disjoint:

S = \bigcup_{A \in S/\sim} A, \qquad A_1 \cap A_2 = \emptyset \ \text{ whenever } A_1 \neq A_2 \text{ in } S/{\sim}.

An equivalence relation therefore breaks $S$ into pairwise disjoint non-empty pieces. Some authors write $S = \bigsqcup_{A \in S/\sim} A$ for a union whose parts are known to be disjoint.

Problem 6.9.

Let $\sim$ be an equivalence relation on $S$ . Show that $x \in [x]$ for every $x \in S$ , and that if $y \in [x]$ then $[y] = [x]$ .

Problem 6.10 (Informal).

Assuming you know the real numbers and the whole numbers, let $x \sim y$ mean that $x - y$ is a whole number. Check that $\sim$ is an equivalence relation on the real numbers, and describe $[0]$ and $\bigl[\tfrac{1}{2}\bigr]$ .

Problem 6.11.

Let $f : S \to T$ be a map and declare $x \sim y$ on $S$ when $f(x) = f(y)$ . Show that $\sim$ is an equivalence relation, and that $S/{\sim}$ is in bijection with the image $f(S)$ .

From Equivalence Relations to Partitions

An equivalence relation gives a partition, and a partition gives an equivalence relation. We prove each direction in turn.

Theorem 6.29 (Equivalence relations induce partitions).

Let $\sim$ be an equivalence relation on a non-empty set $S$ . Then the family of its equivalence classes is a partition of $S$ , called the partition induced by $\sim$ .

Discussion.

We check the three conditions in the definition of a partition: blocks non-empty, blocks pairwise disjoint, blocks covering $S$ . Non-emptiness is immediate, since reflexivity puts $x$ in $[x]$ . Disjointness is the previous proposition read contrapositively: if two classes meet they are equal, so distinct classes cannot meet. For the cover, the same reflexivity observation puts every $s$ in the block $[s]$ , while the reverse inclusion is automatic because every class is a subset of $S$ . One class may have many labels, since $[x] = [y]$ whenever $x \sim y$ , so we index the family by the distinct classes and do not count one block twice.

Proof.

Write the distinct classes as an indexed family $\{C_i\}_{i \in I}$ .

Each $C_i$ is non-empty: if $C_i = [x]$ then $x \in [x]$ by reflexivity. If $i \neq j$ then $C_i \neq C_j$ , so $C_i \cap C_j = \emptyset$ by the previous proposition. Every $C_i$ is a subset of $S$ , so the union of the $C_i$ is contained in $S$ ; and if $s \in S$ then $s \in [s]$ by reflexivity, and $[s]$ is one of the $C_i$ , so $s$ lies in the union. Hence the union is $S$ , and the family is a partition.

Example 6.30.

The relation $R_1$ on $\{1,2,3,4\}$ induces the partition $\bigl\{\{1,2\}, \{3\}, \{4\}\bigr\}$ , which is the list of classes computed above.

Theorem 6.31 (Partitions induce equivalence relations).

Let $\Pi$ be a partition of a set $S$ , and for $x, y \in S$ declare $x \sim y$ to mean that $x$ and $y$ lie in the same block of $\Pi$ . Then $\sim$ is an equivalence relation on $S$ , and the partition it induces is $\Pi$ itself.

Discussion.

There are two claims. For the first, the three properties come from the three conditions on a partition. Reflexivity uses the cover, since every $x$ lies in some block. Symmetry is immediate, since “same block” does not depend on which element is named first. Transitivity uses disjointness: if $x$ and $y$ share a block and $y$ and $z$ share a block, then $y$ lies in both, so the two blocks meet and are therefore the same block, which then holds $x$ and $z$ . For the second claim, fix $x$ and let $A$ be the block holding it. Then $y \in [x]$ exactly when $y$ shares a block with $x$ , which is exactly when $y \in A$ ; so the class $[x]$ is the block $A$ , and the family of classes is $\Pi$ .

Proof.

Write $\Pi = \{A_i\}_{i \in I}$ , so the $A_i$ are non-empty, pairwise disjoint, and their union is $S$ .

For reflexivity, an $x \in S$ lies in some $A_i$ by the cover, so $x \sim x$ . For symmetry, if $x \sim y$ then both lie in some $A_i$ , so both lie in it in the other order and $y \sim x$ . For transitivity, if $x \sim y$ and $y \sim z$ then $x, y \in A_i$ and $y, z \in A_j$ for some $i, j$ ; then $y \in A_i \cap A_j$ , so $i = j$ since distinct blocks are disjoint, and $x, z \in A_i$ gives $x \sim z$ . So $\sim$ is an equivalence relation.

For the second claim, let $x \in S$ and let $A$ be the block holding $x$ , unique because distinct blocks are disjoint. Then $y \in [x]$ if and only if $y \sim x$ , which holds if and only if $y \in A$ . So $[x] = A$ , and the family of classes is exactly $\Pi$ .

Problem 6.12.

Take the partition $\bigl\{\{1,2\}, \{3\}, \{4\}\bigr\}$ of $\{1,2,3,4\}$ and write down every pair in the equivalence relation it induces. Check that you recover $R_1$ .

Problem 6.13.

How many equivalence relations are there on a set with three elements? Count the partitions, then appeal to the two theorems.

The Order on the Natural Numbers

We now define the order on the natural numbers from addition. Throughout this section we work in $\mathbb{N}_0$ , which is a Peano system under $s$ , so all five conditions and the recursion theorem apply. Addition already suggests the order: $n$ lies beyond $m$ when it is reached from $m$ by adding something positive.

Definition 6.32 (Order on the natural numbers).

For $m, n \in \mathbb{N}_0$ we define $m < n$ to hold if and only if there is a $b \in \mathbb{N}$ with $n = m + b$ ; in symbols,

m < n \iff \exists b \in \mathbb{N}\,(n = m + b).

Since $0 \notin \mathbb{N}$ , the difference $b$ is required to be positive. Admitting $b = 0$ would make every number less than itself and break trichotomy.

Corollary 6.33 (Adding a positive element moves you up).

If $x \in \mathbb{N}_0$ and $y \in \mathbb{N}$ then $x < x + y$ . In particular $m < s(m)$ for every $m \in \mathbb{N}_0$ .

Proof.

Take $n = x + y$ in the definition. For the second claim take $y = 1$ , which lies in $\mathbb{N}$ , and recall $m + 1 = s(m)$ .

The definition is stated in terms of differences, so we first show that a difference is unique.

Proposition 6.34 (Uniqueness of differences).

Let $a, b \in \mathbb{N}_0$ . Then $a + x = b$ has at most one solution $x \in \mathbb{N}_0$ .

Discussion.

Uniqueness statements are proved by assuming two solutions and forcing them to agree, so we let $A(a)$ be the statement that any two solutions for that $a$ coincide, and induct on $a$ . The base case is immediate, since $0 + x = b$ reads $x = b$ by addition from the left. For the step we take $s(a) + x_1 = b = s(a) + x_2$ ; both sides are successors, of $a + x_1$ and of $a + x_2$ , and the third Peano condition strips a successor from an equation, leaving an equation the inductive hypothesis handles.

Proof.

We induct on $a$ . For $a = 0$ , the equation $0 + x = b$ gives $x = b$ by addition from the left, so there is at most one solution.

Suppose the claim holds for $a$ and that $s(a) + x_1 = b = s(a) + x_2$ . By addition from the left, $s(a) + x_i = s(a + x_i)$ , so $s(a + x_1) = s(a + x_2)$ ; the third Peano condition gives $a + x_1 = a + x_2$ , and the inductive hypothesis gives $x_1 = x_2$ . Induction completes the proof.

To decide whether $m \leqslant n$ we do not need the case split in the definition of the associated order: one difference is enough, provided we now allow it to be $0$ .

Proposition 6.35 (The associated order on the natural numbers).

For $m, n \in \mathbb{N}_0$ we have $m \leqslant n$ if and only if $n = m + b$ for some $b \in \mathbb{N}_0$ .

Discussion.

The statement is a biconditional, so there are two conditionals. Going forwards, the definition of $\leqslant$ unfolds $m \leqslant n$ into the two cases $m < n$ and $m = n$ , and we must produce a difference in each: the first hands us one directly, and in the second $b = 0$ works. Going backwards we are given a difference and must decide which half of $\leqslant$ holds, so we split on whether $b$ is $0$ ; if it is then $m = n$ , and if it is not then $b \in \mathbb{N}$ and the definition of $<$ applies. Either way $m \leqslant n$ .

Proof.

Suppose $m \leqslant n$ . Then $m < n$ or $m = n$ . In the first case the definition of $<$ supplies $b \in \mathbb{N}$ with $n = m + b$ ; in the second, $b = 0$ serves, since $m + 0 = m = n$ . Either way $b \in \mathbb{N}_0$ .

Conversely suppose $n = m + b$ with $b \in \mathbb{N}_0$ . If $b = 0$ then $m = n$ , so $m \leqslant n$ . If $b \neq 0$ then $b \in \mathbb{N}$ , so $m < n$ and again $m \leqslant n$ .

When $m \leqslant n$ the $b$ with $m + b = n$ is unique, by the proposition on differences, and we write it $n - m$ . So subtraction is defined exactly when the answer lies in $\mathbb{N}_0$ .

Proposition 6.36 (Positive means greater than zero).

Let $n \in \mathbb{N}_0$ . Then $n > 0$ if and only if $n \in \mathbb{N}$ . Consequently $0 \leqslant n$ for every $n \in \mathbb{N}_0$ .

Discussion.

Both directions run through the one equation $n = 0 + b$ . Going forwards we must produce a difference witnessing $0 < n$ , and $b = n$ satisfies the equation, lying in $\mathbb{N}$ because that is the hypothesis. Going backwards the definition hands us a $b \in \mathbb{N}$ with $n = 0 + b$ , so $n$ and $b$ are the same element and the hypothesis transfers. The consequence follows: an element of $\mathbb{N}_0$ is either $0$ , where equality serves, or lies in $\mathbb{N}$ , where the biconditional gives $0 < n$ .

Proof.

Suppose $n \in \mathbb{N}$ . Then $n = 0 + n$ by addition from the left, and $n \in \mathbb{N}$ , so $0 < n$ by the definition of $<$ .

Conversely suppose $0 < n$ . The definition gives $b \in \mathbb{N}$ with $n = 0 + b$ , so $n = b \in \mathbb{N}$ .

Finally, an $n \in \mathbb{N}_0$ is either $0$ or a member of $\mathbb{N}$ ; in the first case $0 = n$ and in the second $0 < n$ , so $0 \leqslant n$ in both.

The proof that $<$ is an order splits $\mathbb{N}_0$ at a chosen element, and we use the same splitting later for the induction variants and for well-ordering, so we give it a name.

Definition 6.37 (Cuts).

For $a \in \mathbb{N}_0$ we write

L_a \defeq \{x \in \mathbb{N}_0 \mid x < a\}, \qquad R_a \defeq \{x \in \mathbb{N}_0 \mid x \geqslant a\}.

Theorem 6.38 (The natural numbers are strictly ordered).

The relation of the definition above is a strict linear order on $\mathbb{N}_0$ .

Discussion.

The definition of a strict linear order wants transitivity and trichotomy, and the characterisation proved earlier lets us replace the second by weak trichotomy and anti-reflexivity, so there are three things to prove. Transitivity is a calculation: two positive differences add up to a single one, which is positive by closure. Anti-reflexivity follows from uniqueness of differences, since $a < a$ would exhibit $a$ as $a + x$ with $x$ positive while $a = a + 0$ exhibits it with difference $0$ , and only one difference is permitted. Weak trichotomy is the main part; in terms of the cuts it is the set equation $L_a \cup R_a = \mathbb{N}_0$ , which we prove by induction on $a$ . The base case is the proposition just proved, since every element is at least $0$ , so $R_0$ is everything. For the step we take an arbitrary $x$ , use the hypothesis to place it on one side of $a$ , and then place it relative to $s(a)$ : an $x$ below $a$ stays below $s(a)$ , an $x$ equal to $a$ falls below $s(a)$ , and for an $x$ above $a$ the positive difference has a predecessor, which gives $s(a) \leqslant x$ .

Proof.

For transitivity, suppose $a + x = b$ and $b + y = c$ with $x, y \in \mathbb{N}$ . Then $a + (x + y) = (a + x) + y = b + y = c$ by the laws of addition, and $x + y \in \mathbb{N}$ by closure; hence $a < c$ .

For anti-reflexivity, $a < a$ would give $a + x = a = a + 0$ with $x \in \mathbb{N}$ , and uniqueness of differences forces $x = 0$ , contradicting $x \in \mathbb{N}$ .

For weak trichotomy, fix $a$ and consider the cuts. We show $L_a \cup R_a = \mathbb{N}_0$ by induction on $a$ . For $a = 0$ , every element satisfies $0 \leqslant x$ by the proposition above, so $R_0 = \mathbb{N}_0$ .

Suppose $L_a \cup R_a = \mathbb{N}_0$ and let $x \in \mathbb{N}_0$ . If $x \in L_a$ then $x < a < s(a)$ by the corollary above, so $x \in L_{s(a)}$ by transitivity. If $x \in R_a$ there are two cases. If $x = a$ then $x < s(a)$ , so $x \in L_{s(a)}$ . If $a < x$ then $x = a + b$ with $b \in \mathbb{N}$ , and $b$ has a predecessor by the theorem on predecessors, say $b = s(c) = c + 1$ ; then $x = a + (1 + c) = s(a) + c$ , so $s(a) \leqslant x$ and $x \in R_{s(a)}$ . Induction gives $L_a \cup R_a = \mathbb{N}_0$ for every $a$ , which is weak trichotomy.

The characterisation of strict linear orders now applies.

Nothing lies strictly between $n$ and its successor. This looks obvious, but it has to be proved from the definition.

Proposition 6.39 (Nothing between n and its successor).

Let $n \in \mathbb{N}_0$ . There is no $x \in \mathbb{N}_0$ with $n < x < s(n)$ .

Discussion.

This is a non-existence claim, so we suppose such an $x$ exists and derive a contradiction. The two strict inequalities give two positive differences, $x = n + b$ and $s(n) = x + c$ , and we eliminate $n$ between them. Since $b$ is positive it has a predecessor, so $b = 1 + d$ , so the $s(n)$ of the second equation appears inside the first. Substituting turns $x$ into $x + (c + d)$ , so $x$ carries the two differences $0$ and $c + d$ ; uniqueness forces $c + d = 0$ , and a sum is zero only when both parts are, so $c = 0$ , contradicting the choice of $c$ as positive.

Proof.

Suppose $n < x$ and $x < s(n)$ . The first gives $b \in \mathbb{N}$ with $x = n + b$ , the second gives $c \in \mathbb{N}$ with $s(n) = x + c$ . Since $b \neq 0$ it has a predecessor, so $b = 1 + d$ for some $d \in \mathbb{N}_0$ . Then

x = n + b = n + (1 + d) = (n + 1) + d = s(n) + d = (x + c) + d = x + (c + d).

So $x + 0 = x + (c + d)$ , and uniqueness of differences gives $c + d = 0$ ; hence $c = 0$ , contradicting $c \in \mathbb{N}$ .

Problem 6.14.

Show that the only $x \in \mathbb{N}_0$ with $x < 2$ are $x = 0$ and $x = 1$ .

Problem 6.15.

Prove that $m < n$ if and only if $s(m) \leqslant n$ , for all $m, n \in \mathbb{N}_0$ .

Problem 6.16.

Let $x, y, z \in \mathbb{N}_0$ , with multiplication as in the problems of the last chapter.

If $x \leqslant y$ then $x + z \leqslant y + z$ , and $x < y$ if and only if $x + z < y + z$ .
If $x \leqslant y$ then $x \cdot z \leqslant y \cdot z$ ; and if moreover $z > 0$ and $x < y$ , then $x \cdot z < y \cdot z$ .
If $x \cdot z < y \cdot z$ then $x < y$ .
If $x \cdot z = y \cdot z$ and $z \neq 0$ , then $x = y$ .

Problem 6.17.

Suppose $m_1 < m_2$ and $n_1 < n_2$ in $\mathbb{N}_0$ . Show that $m_1 + n_1 < m_2 + n_2$ .

Problem 6.18.

Show that $n - n = 0$ and $n - 0 = n$ for every $n \in \mathbb{N}_0$ , and that $n - m = 0$ implies $n = m$ for all $m, n \in \mathbb{N}_0$ with $m \leqslant n$ .

Problem 6.19.

Let $x, y, z, c \in \mathbb{N}_0$ .

If $y \leqslant x$ and $z \leqslant x$ , then $x - y = z$ if and only if $x - z = y$ .
If $z \leqslant y$ then $(x + y) - z = x + (y - z)$ .
If $y \leqslant x$ then $x - y = (x + c) - (y + c)$ .

Problem 6.20.

State the hypotheses on $a, b, c \in \mathbb{N}_0$ under which each of

a + (b - a) = b, \qquad (b - a) + (c - b) = c - a, \qquad c(b - a) = cb - ca

is defined, and prove all three.

Problem 6.21.

Determine all $x, y, z \in \mathbb{N}_0$ for which $(x - y) - z$ and $x - (y - z)$ are both defined, and decide whether the two agree whenever both are.
Decide whether $x - (y + z) = (x - y) - z$ whenever the left-hand side is defined.

Well-Ordering and Induction Variants

With the order we can prove the form of induction that starts at an arbitrary natural number.

Theorem 6.40 (Induction from an arbitrary starting point).

Let $n_0 \in \mathbb{N}_0$ and let $A$ be a predicate on $\mathbb{N}_0$ . If $A(n_0)$ holds, and if $A(n) \implies A(s(n))$ for every $n \geqslant n_0$ , then $A(n)$ holds for every $n \geqslant n_0$ .

Discussion.

Ordinary induction starts at $0$ , and the hypotheses say nothing below $n_0$ , so we enlarge the set where $A$ holds until the fifth Peano condition applies. Let $M$ be that set and put $M' \defeq M \cup L_{n_0}$ , adding everything strictly below the starting point. We may assume $n_0 > 0$ , since at $n_0 = 0$ ordinary induction already applies, and then $0 \in L_{n_0} \subset M'$ settles the base case without appealing to $A$ at all. For the step we take $n \in M'$ and compare $s(n)$ with $n_0$ , which trichotomy resolves into three cases: below $n_0$ it lies in the padding, equal to $n_0$ it lies in $M$ by the base hypothesis, and above $n_0$ it forces $n$ itself to be at or above $n_0$ , so $n$ lies in $M$ and the given step applies. Induction then gives $M' = \mathbb{N}_0$ ; since the two cuts are disjoint and exhaust everything, the added part $L_{n_0}$ has nothing at or above $n_0$ , and $R_{n_0} \subset M$ is what remains.

Proof.

Let $M \defeq \{n \in \mathbb{N}_0 \mid A(n)\}$ and put $M' \defeq M \cup L_{n_0}$ . It is enough to prove $M' = \mathbb{N}_0$ , for then $L_{n_0} \cup R_{n_0} = \mathbb{N}_0$ and $L_{n_0} \cap R_{n_0} = \emptyset$ give $R_{n_0} \subset M$ , which is the assertion.

We may assume $n_0 > 0$ , since $n_0 = 0$ is ordinary induction. Then $0 \in L_{n_0} \subset M'$ . Let $n \in M'$ and compare $s(n)$ with $n_0$ .

If $s(n) < n_0$ then $s(n) \in L_{n_0} \subset M'$ . If $s(n) = n_0$ then $s(n) \in M$ by the base hypothesis. If $s(n) > n_0$ then $n \geqslant n_0$ , since $n < n_0$ would put $n_0$ strictly between $n$ and $s(n)$ ; hence $n \notin L_{n_0}$ , so $n \in M$ , and the induction hypothesis gives $s(n) \in M$ .

In every case $s(n) \in M'$ , so the fifth Peano condition gives $M' = \mathbb{N}_0$ .

Theorem 6.41 (Well-ordering of the natural numbers).

Every non-empty subset $M \subset \mathbb{N}_0$ has a smallest element: there is $m_0 \in M$ with $m_0 \leqslant m$ for every $m \in M$ . We write $m_0 = \min M$ .

Discussion.

A non-empty $M$ may be unbounded, so we first cut it down to a bounded piece. Choose any $a \in M$ and put $M' \defeq L_{s(a)} \cap M$ , which holds $a$ and so is non-empty. A smallest element of $M'$ is already smallest in $M$ , since everything in $M$ outside $L_{s(a)}$ is at least $s(a)$ and therefore above it. So we may assume $M \subset L_{s(a)}$ and induct on $a$ , taking for $A(a)$ the statement that every non-empty subset of $L_{s(a)}$ has a smallest element. The base case can be checked directly: $L_1$ is $\{0\}$ , so the only non-empty subset is $\{0\}$ . For the step, take a non-empty subset of $L_{s(s(a))}$ and intersect it with $L_{s(a)}$ ; if the intersection is empty then nothing between $s(a)$ and its successor leaves only $\{s(a)\}$ , and otherwise the hypothesis supplies a smallest element of the intersection, which by the cutting-down argument is smallest in the whole set.

Proof.

Choose $a \in M$ and put $M' \defeq L_{s(a)} \cap M$ ; since $a < s(a)$ we have $a \in M'$ , so $M'$ is non-empty. If $m_0$ is smallest in $M'$ then $m_0 \leqslant a$ , while every member of $M \setminus M'$ is at least $s(a)$ and hence above $m_0$ ; so $m_0$ is smallest in $M$ . It therefore suffices to show, by induction on $a$ , that every non-empty subset of $L_{s(a)}$ has a smallest element.

For $a = 0$ , the cut $L_1$ is $\{0\}$ : an $x < 1$ cannot be positive, since $0 < x < 1$ would put $x$ strictly between $0$ and its successor. So the only non-empty subset of $L_1$ is $\{0\}$ , whose smallest element is $0$ .

Suppose every non-empty subset of $L_{s(a)}$ has a smallest element, and let $N \neq \emptyset$ be contained in $L_{s(s(a))}$ . If $N \cap L_{s(a)} = \emptyset$ then every element of $N$ is at least $s(a)$ and below $s(s(a))$ , so $N = \{s(a)\}$ and $s(a)$ is its smallest element. Otherwise $N \cap L_{s(a)}$ has a smallest element $m_0$ , and the argument of the first paragraph shows $m_0$ is smallest in $N$ . Induction completes the proof.

Corollary 6.42 (Method of infinite descent).

No non-empty subset $M \subset \mathbb{N}_0$ has the property that every $a \in M$ admits an $a' \in M$ with $a' < a$ .

Proof.

If such an $M$ existed, well-ordering would give it a smallest element $a_0$ , and the hypothesis would supply $a_0' \in M$ with $a_0' < a_0$ , contradicting minimality.

One cannot descend for ever through a non-empty set of natural numbers. The Greeks already used this as a proof technique, and we shall use it when we come to the numbers that are not fractions.

Theorem 6.43 (Strong induction).

Let $A$ be a predicate on $\mathbb{N}_0$ with $A(0)$ true, and suppose that for every $n \in \mathbb{N}_0$ the truth of $A(m)$ for all $m \leqslant n$ implies $A(s(n))$ . Then $A(n)$ holds for every $n \in \mathbb{N}_0$ .

Discussion.

In ordinary induction the step uses only the previous case; here it may use all earlier cases at once, and we prove this from well-ordering. Instead of building up the set where $A$ holds we look at the set where it fails: assume it non-empty and let $n_0$ be its smallest element. The base hypothesis rules out $n_0 = 0$ , so $n_0$ has a predecessor $p$ . Minimality says $A(m)$ holds for every $m < n_0$ , and since nothing lies strictly between $p$ and $n_0$ , those $m$ are precisely the $m \leqslant p$ , which is what the step needs at $p$ . The step therefore yields $A(s(p))$ , that is $A(n_0)$ , and $n_0$ was chosen to make $A$ fail.

Proof.

Let $M \defeq \{n \in \mathbb{N}_0 \mid A(n) \text{ fails}\}$ and suppose $M \neq \emptyset$ . Well-ordering gives it a smallest element $n_0$ , so $A(n_0)$ fails while $A(n)$ holds for every $n < n_0$ .

Since $A(0)$ holds, $n_0 \neq 0$ , so the theorem on predecessors gives $n_0 = s(p)$ for some $p$ . Every $m \leqslant p$ satisfies $m < n_0$ , since $p < s(p) = n_0$ and nothing lies strictly between; hence $A(m)$ holds for every such $m$ . The hypothesis then gives $A(s(p))$ , that is $A(n_0)$ , a contradiction. So $M = \emptyset$ .

Problem 6.22.

Deduce the fifth Peano condition from strong induction, so that the two induction principles are equivalent.

Problem 6.23.

Show that strong induction can be proved without well-ordering, by applying ordinary induction to the set $B \defeq \{n \in \mathbb{N}_0 \mid A(m) \text{ holds for every } m \leqslant n\}$ .

Problem 6.24.

Let $f : \mathbb{N}_0 \to \mathbb{N}_0$ .

Show that $f(s(n)) < f(n)$ cannot hold for every $n \in \mathbb{N}_0$ .
Show that if $f(s(n)) \leqslant f(n)$ for every $n \in \mathbb{N}_0$ , then there is an $N$ with $f(n) = f(N)$ for every $n \geqslant N$ .

Problem 6.25.

Let $n \in \mathbb{N}_0$ . Show that there is exactly one $m \in \mathbb{N}_0$ with $m \cdot m \leqslant n < s(m) \cdot s(m)$ .

Division with Remainder

A first use of well-ordering: dividing one natural number by another leaves a quotient and a remainder, both determined by the two numbers.

Theorem 6.44 (Division with remainder).

Let $n \in \mathbb{N}_0$ and $m \in \mathbb{N}$ . Then there is exactly one pair $q, r \in \mathbb{N}_0$ with

n = q \cdot m + r, \qquad r < m.

Discussion.

An “exactly one” claim asks for existence and uniqueness, and the two need different arguments. For existence we look for the remainder rather than the quotient: the set of numbers of the form $n - q \cdot m$ that remain in $\mathbb{N}_0$ is non-empty, since $q = 0$ leaves $n$ itself, so well-ordering gives us its least member $r$ , and minimality forces $r < m$ : were $r$ at least $m$ we could subtract one more $m$ and get something smaller still. For uniqueness we assume two decompositions and show that a certain multiple of $m$ must be $0$ . Subtracting gives a multiple of $m$ equal to a difference of two remainders, and that difference is below $m$ because each remainder is; but a non-zero multiple of $m$ is at least $m$ , so the multiple is $0$ , the quotients agree, and the remainders follow.

Proof.

For existence, let $R \defeq \{r \in \mathbb{N}_0 \mid n = q \cdot m + r \text{ for some } q \in \mathbb{N}_0\}$ . Taking $q = 0$ gives $n \in R$ , so $R$ is non-empty and well-ordering supplies $r \defeq \min R$ , with $n = q \cdot m + r$ for some $q$ .

Suppose $r \geqslant m$ . Then $r = m + r'$ for some $r' \in \mathbb{N}_0$ , so $n = q \cdot m + m + r' = s(q) \cdot m + r'$ , putting $r' \in R$ ; and $r' < r$ , since $m$ is positive. That contradicts minimality, so $r < m$ .

For uniqueness, suppose $q_1 \cdot m + r_1 = q_2 \cdot m + r_2$ with $r_1, r_2 < m$ , and take $q_1 \geqslant q_2$ without loss. Then $q_1 = q_2 + d$ for some $d \in \mathbb{N}_0$ , and cancelling gives $d \cdot m + r_1 = r_2$ , so $d \cdot m \leqslant r_2 < m$ . If $d$ were positive then $d \geqslant 1$ and $d \cdot m \geqslant m$ , a contradiction; so $d = 0$ , whence $q_1 = q_2$ and then $r_1 = r_2$ .

Corollary 6.45 (Remainder classes).

Let $m \in \mathbb{N}$ . Every $n \in \mathbb{N}_0$ has exactly one of the $m$ forms $k \cdot m$ , $k \cdot m + 1$ , …, $k \cdot m + (m-1)$ with $k \in \mathbb{N}_0$ .

Proof.

The theorem gives exactly one pair $k, r$ with $n = k \cdot m + r$ and $r < m$ , and the values available to $r$ are precisely $0, 1, \ldots, m-1$ .

Taking $m = 2$ splits $\mathbb{N}_0$ into the even numbers, those of the form $2k$ , and the odd ones, those of the form $2k + 1$ ; the corollary says every natural number is one or the other and none is both.

Problem 6.26.

Let $n, m \in \mathbb{N}_0$ with $m$ positive. Show that $m$ divides $n$ , in the sense that $n = k \cdot m$ for some $k \in \mathbb{N}_0$ , exactly when the remainder of the theorem is $0$ .

Problem 6.27.

Show that divisibility orders $\mathbb{N}$ as a partial order in the sense of Definition 6.16 , and find the minimum and the maximum, if they exist, of $\{n \in \mathbb{N} \mid n \text{ divides } 12\}$ in that order.

Descent in Action

Here is an application of infinite descent.

Proposition 6.46 (Odd squares are odd).

Let $n \in \mathbb{N}_0$ . If $n \cdot n$ is even then $n$ is even.

Discussion.

We prove the contrapositive, which is the easier direction to compute with: an odd $n$ is $2k+1$ by the remainder classes, and squaring it and collecting terms exhibits the result as twice something plus one. Only the laws of addition and multiplication are needed; the remainder classes turn “not even” into the usable form $2k + 1$ .

Proof.

Suppose $n$ is odd, so $n = 2k + 1$ for some $k \in \mathbb{N}_0$ by the remainder classes. Then

n \cdot n = (2k + 1)(2k + 1) = 2\bigl(2 \cdot k \cdot k + k + k\bigr) + 1,

which is odd. So an even $n \cdot n$ forces $n$ to be even.

Theorem 6.47 (Two is not a ratio of squares).

There are no $d, a \in \mathbb{N}$ with $d \cdot d = 2 \cdot (a \cdot a)$ .

Discussion.

We argue by contradiction, using infinite descent, so we build a non-empty set in which every member has a smaller member. Suppose some pair works and let $M$ be the set of all $a \in \mathbb{N}$ admitting a partner $d$ ; the supposition puts something in $M$ . The descent comes from using parity twice. From $d \cdot d = 2(a \cdot a)$ the square $d \cdot d$ is even, so $d$ is even by the proposition above; writing $d = 2d'$ and substituting makes $a \cdot a$ even, hence $a$ even too, say $a = 2a'$ . Cancelling a factor of four leaves $d' \cdot d' = 2(a' \cdot a')$ , which puts $a'$ in $M$ as well, and $a' < a$ because halving a positive number decreases it. Infinite descent forbids this.

In terms of fractions, which we have not built yet, this says that no fraction squares to two.

Proof.

Suppose such a pair exists and let $M \defeq \{a \in \mathbb{N} \mid d \cdot d = 2 \cdot (a \cdot a) \text{ for some } d \in \mathbb{N}\}$ , which is then non-empty.

Let $a \in M$ with partner $d$ . Then $d \cdot d$ is even, so $d = 2d'$ by the proposition above. Substituting gives $4(d' \cdot d') = 2(a \cdot a)$ , so $a \cdot a = 2(d' \cdot d')$ ; hence $a \cdot a$ is even and $a = 2a'$ for some $a'$ . Substituting again gives $4(d' \cdot d') = 2 \cdot 4 (a' \cdot a')$ , so $d' \cdot d' = 2(a' \cdot a')$ , putting $a' \in M$ . Since $a = 2a' = a' + a'$ with $a'$ positive, we have $a' < a$ .

So every member of $M$ has a smaller member, which infinite descent forbids. Hence no such pair exists.

Problem 6.28.

Show that there are no $d, a \in \mathbb{N}$ with $d \cdot d = 3 \cdot (a \cdot a)$ , and decide whether the same argument rules out $d \cdot d = 4 \cdot (a \cdot a)$ .

Expansions in a Base

Writing a number in base $g$ is repeated division with remainder, and the digits are the remainders.

Theorem 6.48 (Expansion in a base).

Let $g \in \mathbb{N}$ with $g \geqslant 2$ . For every $n \in \mathbb{N}$ there are uniquely determined $r \in \mathbb{N}_0$ and $a_0, \ldots, a_r \in \mathbb{N}_0$ with $a_r \neq 0$ and $a_\rho < g$ for each $\rho$ , such that

n = a_0 + a_1 g + a_2 g^2 + \cdots + a_r g^r = \sum_{\rho = 0}^{r} a_\rho g^\rho.

Discussion.

The digits come from dividing repeatedly: set $q_0 = n$ , divide by $g$ to leave the lowest digit $a_0$ and a quotient $q_1$ , divide that to leave $a_1$ , and so on. Two things must be checked. It stops because $g \geqslant 2$ makes each non-terminal quotient strictly smaller than the number it came from, and a scheme that never halted would descend for ever through $\mathbb{N}_0$ , which descent forbids. The digits add back to $n$ because each equation expresses one quotient in terms of the next, so substituting upwards leaves the displayed sum. Uniqueness runs the same divisions in reverse: division with remainder determines $a_0$ and $q_1$ from $n$ , then $a_1$ and $q_2$ from $q_1$ , and so on, fixing the leading digit and the final index along with the rest.

Proof.

Put $q_0 \defeq n$ and apply division with remainder repeatedly:

\begin{aligned} q_0 &= q_1 g + a_0, & a_0 &< g, \\ q_1 &= q_2 g + a_1, & a_1 &< g, \\ &\ \,\vdots \\ q_{r-1} &= q_r g + a_{r-1}, & a_{r-1} &< g, \\ q_r &= a_r, & 0 < a_r &< g. \end{aligned}

Each line is division with remainder applied to $q_\rho$ and $g$ . Since $g \geqslant 2$ , a non-zero quotient satisfies $q_{\rho+1} < q_\rho$ , so the scheme cannot run for ever without contradicting infinite descent; it therefore halts at some $r$ with $q_r < g$ .

Substituting each line into the one above it gives $n = a_0 + a_1 g + \cdots + a_r g^r$ . Uniqueness of the quotient and remainder at each step gives uniqueness of the list of digits, and of $r$ .

We write $n = (a_r \ldots a_0)_g$ , and call the cases $g = 2$ and $g = 10$ the binary and decimal expansions. The value can be recovered by a recursion which never computes a power separately:

n = \Bigl(\cdots\bigl((a_r g + a_{r-1})g + a_{r-2}\bigr)g + \cdots + a_1\Bigr)g + a_0.

This is Horner’s scheme for base $g$ . It uses one multiplication by $g$ at each stage, $r$ in all, where computing every power first and then forming every term uses up to twice as many.

Problem 6.29.

Write $1000$ in base $7$ , and write $(110\,1101)_2$ in base $10$ .

Problem 6.30.

Let $n \in \mathbb{N}$ and let $r$ be as in the theorem. Show that $g^r \leqslant n < g^{s(r)}$ .

The Maximum Principle

Well-ordering says every non-empty subset of $\mathbb{N}_0$ has a minimum. The dual statement is false as it stands, since $\mathbb{N}_0$ itself has no maximum, but it becomes true once an upper bound is present.

Theorem 6.49 (Maximum principle).

Let $W \subset \mathbb{N}_0$ be non-empty with an upper bound in $\mathbb{N}_0$ . Then $W$ has a maximum.

Discussion.

We cannot induct on $W$ , which is an arbitrary set, so we induct on the bound instead: let $T$ be the set of those $B$ such that every non-empty subset bounded above by $B$ has a maximum, and aim at $T = \mathbb{N}_0$ ; once that is known, any upper bound of the given $W$ lies in $T$ and gives $W$ a maximum. The base case can be checked directly, since a set bounded above by $0$ can only be $\{0\}$ , every element being at least $0$ . For the step we take a non-empty $S$ bounded above by $s(n)$ and split on whether $s(n)$ belongs to $S$ : if it does, it is a bound lying in the set and the previous proposition finishes at once; if it does not, then $n$ is itself an upper bound, because an element strictly above $n$ and at or below $s(n)$ but different from it would sit strictly between $n$ and its successor, which nothing does.

Proof.

Let $T$ be the set of $B \in \mathbb{N}_0$ such that every non-empty $S \subset \mathbb{N}_0$ with upper bound $B$ has a maximum.

For $0 \in T$ : let $S$ be non-empty with upper bound $0$ , and take $k \in S$ . Then $k \leqslant 0$ , while $0 \leqslant k$ , so $k = 0$ by antisymmetry. Hence $S = \{0\}$ , and $0$ is a bound lying in $S$ , so it is the maximum.

Suppose $n \in T$ and let $S$ be non-empty with upper bound $s(n)$ . If $s(n) \in S$ then $s(n)$ is an upper bound lying in $S$ , hence the maximum. If $s(n) \notin S$ , we claim $n$ bounds $S$ : an element $k \in S$ with $n < k$ satisfies $k \leqslant s(n)$ and $k \neq s(n)$ , so $n < k < s(n)$ , which nothing does. So $n$ is an upper bound of $S$ , and $n \in T$ supplies a maximum. Hence $s(n) \in T$ .

By induction $T = \mathbb{N}_0$ . Given $W$ non-empty with upper bound $B$ , we have $B \in T$ , so $W$ has a maximum.

A partially ordered set in which every non-empty subset has a minimum is called well-ordered. By the theorem above $\mathbb{N}_0$ is well-ordered, and so is $\mathbb{N}$ , whose non-empty subsets are non-empty subsets of $\mathbb{N}_0$ . $\mathbb{N}_0$ has two further order properties: every element beyond the minimum has an immediate predecessor, and there is no greatest element. Together with well-ordering these determine the order completely.

Theorem 6.50 (Characterisation of the natural numbers).

Let $M$ be a non-empty well-ordered set in which every element other than $\min M$ has an immediate predecessor, meaning an element $p < a$ with nothing of $M$ strictly between, and which has no greatest element. Then there is an order-preserving bijection from $\mathbb{N}_0$ to $M$ .

Discussion.

The conclusion asks for the order of $\mathbb{N}_0$ inside $M$ , so the plan is to build a successor map on $M$ from the three hypotheses and then check that it reaches everything. In $\mathbb{N}_0$ the successor of $n$ is the least element above $n$ , and that phrase makes sense in $M$ : the absence of a greatest element keeps the set of elements above $a$ non-empty, and well-ordering gives it a minimum, which we call $\nu(a)$ . The predecessor hypothesis makes $\nu$ behave like a successor map, since nothing is reached from below except through an immediate predecessor, so $\min M$ is never a value of $\nu$ and two elements cannot share one. With $\nu$ in hand the recursion theorem builds the candidate: start at $\min M$ and keep applying $\nu$ . As $\nu(a) > a$ , the values climb, which already gives order-preservation and injectivity; the main work is surjectivity, where we take the least element never reached, which cannot exist because its immediate predecessor is reached and $\nu$ carries that to it.

Proof.

Write $m_0 \defeq \min M$ and for $a \in M$ put $\nu(a) \defeq \min\{m \in M \mid a < m\}$ , which exists because $M$ has no greatest element and is well-ordered. By construction $\nu(a) > a$ and nothing of $M$ lies strictly between $a$ and $\nu(a)$ .

An element $c \neq m_0$ has exactly one immediate predecessor: two of them, say $p < q$ , would put $q$ strictly between $p$ and $c$ . Hence $\nu$ is injective, since $\nu(a) = \nu(b) = c$ makes $a$ and $b$ both immediate predecessors of $c$ ; and $m_0$ is not a value of $\nu$ , since $\nu(a) > a \geqslant m_0$ .

The recursion theorem, applied with $a = m_0$ and $g = \nu$ , gives exactly one $f : \mathbb{N}_0 \to M$ with $f(0) = m_0$ and $f(s(n)) = \nu(f(n))$ . Since $\nu(x) > x$ for every $x$ , induction gives $f(a) < f(b)$ whenever $a < b$ ; in particular $f$ is injective.

For surjectivity, let $A$ be the range of $f$ . Then $m_0 \in A$ , and $A$ is closed under $\nu$ , since $\nu(f(n)) = f(s(n))$ . Suppose $M \setminus A$ is non-empty and let $c$ be its least element. Since $m_0 \in A$ we have $c \neq m_0$ , so $c$ has an immediate predecessor $p$ ; by minimality of $c$ we have $p \in A$ , and $c = \nu(p)$ because nothing lies strictly between. Closure of $A$ under $\nu$ gives $c \in A$ , a contradiction. Hence $f$ is a bijection.

Remark.

The proof never carries out an induction inside $M$ : surjectivity uses well-ordering through a least counterexample, and $f$ itself comes from the recursion theorem on $\mathbb{N}_0$ . One may therefore take well-ordering, the predecessor property and the absence of a greatest element as axioms in place of Peano’s; the theorem says the two systems describe the same ordered set.

Problem 6.31.

Let $S \subset \mathbb{N}_0$ be non-empty. Prove that $S$ has a minimum by applying the maximum principle to the set of lower bounds of $S$ , rather than by appealing to well-ordering.

Problem 6.32.

State and prove the maximum principle for non-empty subsets of $\mathbb{N}$ bounded above in $\mathbb{N}$ , starting the induction at $1$ .

Problem 6.33.

Let $M$ be an ordered set in which every two-element subset has a minimum. Show that the order is total, and deduce that every well-ordered set is totally ordered.

Problem 6.34.

Let $S \subset \mathbb{N}_0$ be such that for every $c \in \mathbb{N}_0$ there is an $s \in S$ with $s > c$ . Prove that there is exactly one bijection $f : \mathbb{N}_0 \to S$ with $f(m) < f(n)$ whenever $m < n$ .

Problem 6.35.

Order $\mathbb{N}_0 \times \mathbb{N}_0$ by declaring $(a, b) < (c, d)$ when $a < c$ , or when $a = c$ and $b < d$ . Show that this is a strict linear order in which every non-empty subset has a least element.

Problem 6.36.

Theorem 6.50 asks three things of $M$ . Exhibit a well-ordered set with no greatest element in which some element other than the minimum has no immediate predecessor, and a well-ordered set in which every element other than the minimum has an immediate predecessor but a greatest element exists. For the first, name the element that has no immediate predecessor.

Problem 6.37.

Exhibit a totally ordered set $L$ with no greatest element in which every element has an immediate predecessor, and which is not well-ordered.
Show that there is no bijection $f : \mathbb{N}_0 \to L$ with $f(m) < f(n)$ whenever $m < n$ , and say where the proof of Theorem 6.50 uses the hypothesis that $L$ fails.
Order $L \times \mathbb{N}_0$ as in Problem 6.35 . Show that the result is totally ordered but not well-ordered.

Sequences

A list is a function whose inputs are positions. The cuts defined for the natural numbers give us the positions, so nothing new is needed.

Definition 6.51 (Sequence).

Let $A$ be a set. A finite sequence in $A$ of length $n$ is a function from $L_n$ to $A$ , written $(a_i)_{i < n}$ or $(a_0, a_1, \ldots)$ , in the notation already used for tuples; the unique sequence of length $0$ is the empty function, written $(\,)$ . An infinite sequence in $A$ is a function from $\mathbb{N}_0$ to $A$ . We write

\operatorname{Seq}(A) \defeq \bigcup_{n \in \mathbb{N}_0} A^{L_n}

for the set of all finite sequences in $A$ , using the Cartesian power of the last chapter but one.

That $\operatorname{Seq}(A)$ is a set takes a moment. Each $A^{L_n}$ consists of functions from $L_n$ to $A$ , hence of subsets of $\mathbb{N}_0 \times A$ , so all of them lie inside $\mathcal{P}(\mathbb{N}_0 \times A)$ ; comprehension collects them and the union axiom pools them.

Remark.

Some texts say instead that a finite sequence is a function whose domain is a natural number. That is the same definition read through the construction of the last chapter, where $n$ was built as the set holding exactly its predecessors, so that $n = L_n$ . We use the cut, which says the same thing without leaning on which sets the numerals happen to be.

Restriction gives the initial pieces of a sequence: for $f$ defined on $\mathbb{N}_0$ and $n \in \mathbb{N}_0$ , the restriction $f|_{L_n}$ is the finite sequence $(f_0, \ldots)$ of length $n$ , recording everything before position $n$ and nothing else.

The General Recursion Theorem

The recursion theorem of the last chapter lets the next value depend on the previous one, and its parametrised form lets it depend on the index as well. Neither is enough when the next value depends on all the earlier ones at once. With sequences we can state such a rule, and with the order we can prove that it defines a function.

Theorem 6.52 (General recursion).

Let $S$ be a set and let $g : \operatorname{Seq}(S) \to S$ . Then there is exactly one $f : \mathbb{N}_0 \to S$ with

f(n) = g\bigl(f|_{L_n}\bigr) \quad\text{for every } n \in \mathbb{N}_0.

Discussion.

The rule wants the whole history at each step, so we recurse on histories rather than on values: instead of building $f$ directly we build the sequence of its initial pieces. Let $G$ send a pair $(t, n)$ to $t$ extended by the value $g(t)$ at position $n$ , whenever $t$ has length $n$ , and to the empty sequence otherwise; that second clause is bookkeeping only, since the case never arises. Parametrised recursion then gives a map $F$ on $\mathbb{N}_0$ with $F(0)$ the empty sequence and $F(s(n)) = G(F(n), n)$ , and an induction shows $F(n)$ has length exactly $n$ , so the bookkeeping clause is never reached. Each $F(n)$ extends its predecessors, so their union is a single function $f$ on $\mathbb{N}_0$ whose restriction to $L_n$ is $F(n)$ , and reading the construction back gives the required identity. Uniqueness uses strong induction: two solutions agreeing everywhere below $n$ have the same restriction to $L_n$ , so $g$ returns the same value at $n$ , and ordinary induction would not deliver that hypothesis.

Proof.

Define $G : \operatorname{Seq}(S) \times \mathbb{N}_0 \to \operatorname{Seq}(S)$ by

G(t, n) \defeq \begin{cases} t \cup \bigl\{(n, g(t))\bigr\} & \text{if } t \text{ has length } n, \\ (\,) & \text{otherwise.} \end{cases}

By parametrised recursion there is a unique $F : \mathbb{N}_0 \to \operatorname{Seq}(S)$ with $F(0) = (\,)$ and $F(s(n)) = G(F(n), n)$ .

We claim $F(n)$ has length $n$ . This holds at $0$ . If $F(n)$ has length $n$ , then $F(s(n)) = F(n) \cup \{(n, g(F(n)))\}$ , whose domain is $L_n \cup \{n\}$ ; and $L_n \cup \{n\} = L_{s(n)}$ , since $x < s(n)$ holds exactly when $x < n$ or $x = n$ , nothing lying strictly between $n$ and $s(n)$ . So $F(s(n))$ has length $s(n)$ , and induction gives the claim.

Each $F(n)$ is therefore a function extending all the earlier ones, so their union $f \defeq \bigcup_{n \in \mathbb{N}_0} F(n)$ is a function on $\mathbb{N}_0$ with $f|_{L_n} = F(n)$ for every $n$ . Then

f(n) = F(s(n))(n) = g\bigl(F(n)\bigr) = g\bigl(f|_{L_n}\bigr),

which is the required identity.

For uniqueness, let $h$ also satisfy the identity, and suppose $f(m) = h(m)$ for every $m < n$ . Then $f|_{L_n} = h|_{L_n}$ , so $f(n) = g(f|_{L_n}) = g(h|_{L_n}) = h(n)$ . Strong induction gives $f = h$ .

Problem 6.38.

Show that the recursion theorem of the last chapter is a special case of this one: given $a \in S$ and $\gamma : S \to S$ , exhibit a $g : \operatorname{Seq}(S) \to S$ whose solution is the map with $f(0) = a$ and $f(s(n)) = \gamma(f(n))$ .

Problem 6.39.

Let $S$ be a set and $g : \operatorname{Seq}(S) \to S$ . Show that the finite sequences $F(n)$ built in the proof satisfy $F(m) \subset F(n)$ whenever $m < n$ , and explain where that is used.

General Associativity

We can now prove something used without proof earlier. Addition was defined for two arguments and proved associative and commutative for two and three; the notation $a_1 + \cdots + a_n$ assumes more, namely that the brackets and the order may be chosen freely. With finite sequences and induction in hand we can say what that means and prove it.

Fix a left-associated reading once and for all: for a finite sequence $a$ of length $n$ in a Peano system with addition, define

p(a) \defeq \begin{cases} 0 & \text{if } n = 0, \\ p\bigl(a|_{L_{k}}\bigr) + a_{k} & \text{if } n = s(k). \end{cases}

So $p$ of the sequence $(a_0, a_1, a_2)$ is $(0 + a_0 + a_1) + a_2$ , brackets to the left. A full bracketing of $a_0 + \cdots + a_{n-1}$ is either the single term, when $n = 1$ , or a sum $L + R$ in which $L$ is a full bracketing of an initial piece and $R$ is a full bracketing of the rest.

Theorem 6.53 (General associativity and neighbour swaps).

Let $a$ be a finite sequence of length $n$ in a Peano system with addition.

Every full bracketing of $a_0 + \cdots + a_{n-1}$ equals $p(a)$ .
If $b$ is obtained from $a$ by exchanging two neighbouring entries, then $p(b) = p(a)$ .

Discussion.

The first part is an induction on $n$ , but a bracketing may split the sum anywhere, so the step needs one auxiliary fact: the left-associated sum of the whole is the left-associated sum of the first $k$ entries added to that of the rest. That splitting identity is itself a short induction on the length of the second block, using nothing but binary associativity, and with it the step applies the hypothesis to the two halves of the bracketing and adds the results.

Once every bracketing is identified with $p$ , the second part may ignore brackets altogether. Exchanging neighbours rearranges a two-term middle and nothing else, so binary commutativity sorts that middle and the splitting identity puts the rest of the list back around it.

Proof.

We first record the splitting identity: for $k < n$ ,

p(a) = p\bigl(a|_{L_k}\bigr) + p\bigl((a_k, \ldots, a_{n-1})\bigr).

Fix $k$ and induct on the length $m$ of the second block. If $m = 1$ this is the defining clause of $p$ . If it holds at $m$ , then appending one more entry gives

p(a) = p\bigl(a|_{L_{n-1}}\bigr) + a_{n-1} = \Bigl(p\bigl(a|_{L_k}\bigr) + p\bigl((a_k, \ldots, a_{n-2})\bigr)\Bigr) + a_{n-1},

and associativity of addition regroups this as $p(a|_{L_k}) + p((a_k, \ldots, a_{n-1}))$ , which is the identity at $m + 1$ .

For the first part, induct on $n$ . The case $n = 1$ is immediate. Let $P$ be a full bracketing of $a_0 + \cdots + a_{n-1}$ , so $P = L + R$ where $L$ brackets the first $k$ entries and $R$ the rest. The inductive hypothesis gives $L = p(a|_{L_k})$ and $R = p((a_k, \ldots, a_{n-1}))$ , so $P = p(a)$ by the splitting identity.

For the second part, let $b$ exchange the entries at positions $k$ and $s(k)$ . The two-term identity $a_k + a_{s(k)} = a_{s(k)} + a_k$ is commutativity. If the exchanged pair is the whole sequence we are done; otherwise two applications of the splitting identity write $p(a)$ as a sum in which that pair appears as a single middle block, and the same decomposition of $p(b)$ differs only in that block, which commutativity identifies with it.

Brackets therefore no longer matter, and neighbouring summands may be exchanged at will. Any rearrangement of a finite list can be reached by a string of neighbour exchanges, moving each entry past its neighbours until it sits where it should, so the value of a finite sum depends on neither the bracketing nor the order of its terms.

Problem 6.40.

Carry out the same argument for multiplication: define the left-associated product $\pi$ by the clauses $\pi((\,)) \defeq 1$ and $\pi(a) \defeq \pi(a|_{L_k}) \cdot a_k$ when $a$ has length $s(k)$ , and prove both parts of the theorem for it. Which laws replace associativity and commutativity of addition at each step?

Problem 6.41.

Show that any rearrangement of a finite sequence is a string of neighbour exchanges, so that the last sentence above is a theorem rather than an appeal to intuition. (Harder.)

Zorn’s Lemma

Finally, two statements equivalent to the axiom of choice, and the reason some mathematicians do not accept it.

Definition 6.54 (Chains and inductively ordered sets).

Let $M$ be a partially ordered set. A subset $A \subset M$ is a chain if the order $M$ induces on $A$ is a total order, that is, if any two elements of $A$ are comparable. The set $M$ is inductively ordered if every chain in $M$ has an upper bound in $M$ .

Remark.

An inductively ordered set is never empty. The empty subset is a chain, vacuously, so it too must have an upper bound, and an upper bound is an element of $M$ .

Theorem 6.55 (Zorn's lemma).

Every inductively ordered set has at least one maximal element.

Discussion.

We state this without proof. It is not a theorem of the axioms we have listed: on the basis of the rest, Zorn’s lemma is equivalent to the axiom of choice, so proving it would amount to deriving one from the other, and the derivation is long enough to belong to a course in set theory rather than here. Note the form of the statement. The hypothesis is about chains, which are the totally ordered pieces of $M$ , and the conclusion is about a maximal element, which need not be a maximum: nothing says the element found is comparable with everything, only that nothing strictly exceeds it. In a partial order a maximal element need not be a maximum, which is why the conclusion is stated this way.

Remark.

The result is due to Kuratowski, though it carries Zorn’s name; Zorn proved the equivalence with choice and was the first to put the statement to work on algebraic questions.

Theorem 6.56 (Well-ordering theorem).

Every non-empty set can be ordered so that every non-empty subset has a least element.

Discussion.

Again we state without proof, for the same reason: on the basis of the other axioms the well-ordering theorem, Zorn’s lemma and the axiom of choice are all equivalent to one another. Of the three it is the hardest to believe. Well-ordering of $\mathbb{N}_0$ was a theorem we proved, resting on the successor structure; here the claim is that any set whatever admits such an order, however little structure it carries and however unlike the natural numbers it looks.

Remark (Informal).

Assuming you know the real numbers, they are not well-ordered by their usual order: the set of those greater than $0$ has no least element, since any candidate is beaten by something smaller still above $0$ . The well-ordering theorem nevertheless asserts that some other order on them is a well-order. No such order has ever been exhibited, and none can be described explicitly; the theorem asserts that one exists and offers no way to find it.

That gap between existence and construction is what leads some mathematicians to reject the axiom of choice. Our position is to accept it, and to say plainly when we use it.

Problem 6.42.

Show that a maximal element need not be a maximum, by exhibiting a partially ordered set with two maximal elements. Show also that in a total order the two notions coincide.

Problem 6.43.

Let $M$ be a set and consider $\mathcal{P}(M) \setminus \{M\}$ ordered by inclusion. Show that it is inductively ordered when $M$ is non-empty, and identify its maximal elements.

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

The last sheet gave the checker a Peano system to compute in. This chapter needs two more things of it, and only one of them is new. A relation is a set of ordered pairs, and pairs, products and sets are all already there; the order on $\mathbb{N}_0$ is not, and arrives as notation below.

Relations

A relation on $S$ is a subset of $S \times S$ , so $x \mathbin{R} y$ is typed as the membership it abbreviates, (x, y) ∈ R. The three properties of Definition 6.2 are not names the checker knows; they are written out as the statements they are, so symmetry of $R$ enters a problem as the hypothesis

hs : ∀ a b : Obj, (a, b) ∈ R → (b, a) ∈ R

and is used by applying it to two objects and a membership, left to right: hs x y h.

One piece of notation is new. The separation axiom carves a subset out of a set by a criterion, and it is written {x ∈ A | p x}, with the membership criterion the axiom gives: y ∈ {x ∈ A | p x} is y ∈ A ∧ p y, in the way that x ∈ A ∩ B was a conjunction on an earlier sheet. So ⟨_, _⟩ builds a membership and .left and .right take one apart. This is what lets an equivalence class be written down: $[a]$ of Definition 6.26 is {s ∈ S | (s, a) ∈ R}.

Example.

The universal relation on $S$ is reflexive. Membership in a product is a conjunction, and here both halves are the same hypothesis.

Example.

Reflexivity puts $a$ in its own class. The two halves of the criterion are the two things the class asks of $a$ .

Exercise 6.11.

The empty relation is symmetric and transitive.

Exercise 6.12.

And the universal relation is transitive.

Exercise 6.13.

Symmetry and transitivity give reflexivity, but only at the elements the relation already reaches.

lean proof

1example (R x y : Obj)2    (hs : ∀ a b : Obj, (a, b) ∈ R → (b, a) ∈ R)3    (ht : ∀ a b c : Obj, (a, b) ∈ R → (b, c) ∈ R → (a, c) ∈ R)4    (h : (x, y) ∈ R) : (x, x) ∈ R ∧ (y, y) ∈ R := by

5  sorry

goalR x y : Obj hs : ∀ (a : Obj), ∀ (b : Obj), (a, b) ∈ R → (b, a) ∈ R ht : ∀ (a : Obj), ∀ (b : Obj), ∀ (c : Obj), (a, b) ∈ R → (b, c) ∈ R → (a, c) ∈ R h : (x, y) ∈ R ⊢ (x, x) ∈ R ∧ (y, y) ∈ R

Exercise 6.14.

The first half of Problem 6.3 , with $T$ written out.

lean proof

1example (S R x y : Obj)2    (hs : ∀ a b : Obj, (a, b) ∈ R → (b, a) ∈ R)3    (ht : ∀ a b c : Obj, (a, b) ∈ R → (b, c) ∈ R → (a, c) ∈ R)4    (hx : x ∈ S) (h : (x, y) ∈ R) : x ∈ {t ∈ S | (t, t) ∈ R} := by

5  sorry

goalS R x y : Obj hs : ∀ (a : Obj), ∀ (b : Obj), (a, b) ∈ R → (b, a) ∈ R ht : ∀ (a : Obj), ∀ (b : Obj), ∀ (c : Obj), (a, b) ∈ R → (b, c) ∈ R → (a, c) ∈ R hx : x ∈ S h : (x, y) ∈ R ⊢ x ∈ {t ∈ S | (t, t) ∈ R}

Exercise 6.15.

Symmetry survives intersection.

Exercise 6.16.

Proposition 6.22 , with the order written as a relation $L$ and antisymmetry as a hypothesis.

lean proof

1example (S L m n : Obj)2    (hanti : ∀ a b : Obj, (a, b) ∈ L → (b, a) ∈ L → a = b)3    (hm : m ∈ S ∧ ∀ x : Obj, x ∈ S → (m, x) ∈ L)4    (hn : n ∈ S ∧ ∀ x : Obj, x ∈ S → (n, x) ∈ L) : m = n := by

5  sorry

goalS L m n : Obj hanti : ∀ (a : Obj), ∀ (b : Obj), (a, b) ∈ L → (b, a) ∈ L → a = b hm : m ∈ S ∧ (∀ (x : Obj), x ∈ S → (m, x) ∈ L) hn : n ∈ S ∧ (∀ (x : Obj), x ∈ S → (n, x) ∈ L) ⊢ m = n

Exercise 6.17.

The step $2 \implies 1$ of Proposition 6.28 : classes that meet come from related elements.

lean proof

1example (S R a b c : Obj)2    (hs : ∀ x y : Obj, (x, y) ∈ R → (y, x) ∈ R)3    (ht : ∀ x y z : Obj, (x, y) ∈ R → (y, z) ∈ R → (x, z) ∈ R)4    (h : c ∈ {s ∈ S | (s, a) ∈ R} ∩ {s ∈ S | (s, b) ∈ R}) : (a, b) ∈ R := by

5  sorry

goalS R a b c : Obj hs : ∀ (x : Obj), ∀ (y : Obj), (x, y) ∈ R → (y, x) ∈ R ht : ∀ (x : Obj), ∀ (y : Obj), ∀ (z : Obj), (x, y) ∈ R → (y, z) ∈ R → (x, z) ∈ R h : c ∈ {s ∈ S | (s, a) ∈ R} ∩ {s ∈ S | (s, b) ∈ R} ⊢ (a, b) ∈ R

Exercise 6.18.

And the step $1 \implies 3$ , which is an equality of sets.

lean proof

1example (S R a b : Obj)2    (hs : ∀ x y : Obj, (x, y) ∈ R → (y, x) ∈ R)3    (ht : ∀ x y z : Obj, (x, y) ∈ R → (y, z) ∈ R → (x, z) ∈ R)4    (h : (a, b) ∈ R) : {s ∈ S | (s, a) ∈ R} = {s ∈ S | (s, b) ∈ R} := by

5  sorry

goalS R a b : Obj hs : ∀ (x : Obj), ∀ (y : Obj), (x, y) ∈ R → (y, x) ∈ R ht : ∀ (x : Obj), ∀ (y : Obj), ∀ (z : Obj), (x, y) ∈ R → (y, z) ∈ R → (x, z) ∈ R h : (a, b) ∈ R ⊢ {s ∈ S | (s, a) ∈ R} = {s ∈ S | (s, b) ∈ R}

The order on the natural numbers

ℕ is the carrier of the last sheet, and the order is written ≤ and <, typed \le and <. Neither is a name in the library: they are the definitions of Definition 6.32 and Proposition 6.35 outright, so

m ≤ n   is   ∃ b : ℕ, n = m + b
m < n   is   ∃ b : ℕ, b ≠ 0 ∧ n = m + b

and every tactic for an existential acts on them unchanged: use supplies the difference, obtain ⟨b, hb, he⟩ takes a strict inequality apart into a positive $b$ and the equation it satisfies, and obtain ⟨b, he⟩ does the same for a non-strict one. The reverse orders > and ≥ are these two read backwards, as Definition 6.14 has them. Numerals are still spelled as the last sheet spelled them, so $1$ is succ 0.

Example.

The difference that makes an element reach itself is $0$ , and the first clause of addition checks it.

Example.

Corollary 6.33 . Once the difference is named, one half is the hypothesis and the other holds of itself.

Exercise 6.19.

The second half of Proposition 6.36 .

Exercise 6.20.

Every element is below its successor.

Exercise 6.21.

A positive difference is a difference.

Exercise 6.22.

Proposition 6.8 , proved here from uniqueness of differences rather than from trichotomy.

Exercise 6.23.

Transitivity: two positive differences compose into one.

Exercise 6.24.

Antisymmetry, which is the second law of Proposition 6.11 .

Exercise 6.25.

No comparison points both ways.

Exercise 6.26.

The first part of Problem 6.16 .

Exercise 6.27.

And the second, with the factor on the left so that distributivity applies as it stands.

Exercise 6.28.

Problem 6.15 . Both directions move a successor between the two sides of a sum.

Exercise 6.29.

Problem 6.17 .

Exercise 6.30.

Proposition 6.39 . (Harder.)

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic
induction n with k ih	the fifth Peano condition: prove the goal at 0, then at succ k from ih

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are
Nat.succ_inj	∀ {m n : ℕ}, succ m = succ n → m = n — the third Peano condition: the successor is injective
Nat.succ_ne_zero	∀ (n : ℕ), succ n ≠ 0 — the fourth: zero is nobody's successor
Nat.pred	∀ {n : ℕ}, n ≠ 0 → ∃ m : ℕ, n = succ m — predecessors: everything but zero is a successor
Nat.add_zero	∀ (m : ℕ), m + 0 = m — the first clause of addition
Nat.add_succ	∀ (m n : ℕ), m + succ n = succ (m + n) — the second clause of addition
Nat.zero_add	∀ (n : ℕ), 0 + n = n — addition from the left
Nat.succ_add	∀ (m n : ℕ), succ m + n = succ (m + n) — addition from the left, at a successor
Nat.add_assoc	∀ (m n p : ℕ), (m + n) + p = m + (n + p) — addition is associative
Nat.add_comm	∀ (m n : ℕ), m + n = n + m — addition is commutative
Nat.add_ne_zero	∀ {a : ℕ} (b : ℕ), a ≠ 0 → a + b ≠ 0 — positivity is absorbing
Nat.mul_zero	∀ (m : ℕ), m * 0 = 0 — the first clause of multiplication
Nat.mul_succ	∀ (m n : ℕ), m * succ n = m * n + m — the second clause of multiplication
Nat.zero_mul	∀ (m : ℕ), 0 * m = 0 — multiplication from the left
Nat.succ_mul	∀ (m n : ℕ), succ m * n = m * n + n — multiplication from the left, at a successor
Nat.add_right_cancel	∀ {m n k : ℕ}, m + k = n + k → m = n — cancellation, from the last sheet
Nat.add_eq_zero	∀ {m n : ℕ}, m + n = 0 → m = 0 ∧ n = 0 — a sum is zero only when both parts are, from the last sheet
Nat.mul_comm	∀ (m n : ℕ), m * n = n * m — multiplication is commutative, from the last sheet
Nat.mul_add	∀ (m n p : ℕ), m * (n + p) = m * n + m * p — multiplication distributes over addition, from the last sheet
Nat.mul_assoc	∀ (m n p : ℕ), (m * n) * p = m * (n * p) — multiplication associates, from the problems of the last chapter
Nat.add_mul	∀ (m n p : ℕ), (m + n) * p = m * p + n * p — distributivity on the other side
Nat.add_left_cancel	∀ {a m n : ℕ}, a + m = a + n → m = n — uniqueness of differences
Nat.lt_trichotomy	∀ (m n : ℕ), m < n ∨ m = n ∨ n < m — trichotomy, from the theorem that ℕ is strictly ordered

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b