Order

The relations $\leq$ on the numbers, $\subseteq$ on sets and "divides" on the positive integers do not sort things into groups of equals; they rank them, and ranking needs its own definitions of what comes first, what sits on top, and when a collection has a top at all.

The previous lesson picked out the equivalence relations, those that are reflexive (every element is related to itself), symmetric (a relation one way gives it the other way) and transitive (related along a chain means related end to end), and showed that they group things. This lesson turns to the relations that rank. It assumes relations as sets of pairs, power sets, the quantifiers, and divisibility: $a ∣ b$ when $b = a k$ for some integer $k$ . It also uses two results from the lesson on direct proof: the well-ordering principle (every non-empty set of natural numbers has a least element) and the division algorithm. As throughout the course, $ℕ = {1, 2, 3, \dots}$ , and the power set of a set $X$ , the set of all its subsets, is written $P (X)$ .

Antisymmetry and partial orders

An order cannot be symmetric: if $x \leq y$ forced $y \leq x$ , then $1 \leq 2$ would give $2 \leq 1$ . What an order has instead is that two things each ranked below the other are the same thing. A relation $⪯$ on a set $A$ is antisymmetric when

\forall a, b \in A ((a ⪯ b \land b ⪯ a) \Rightarrow a = b)

The symbol $⪯$ stands for an abstract relation of this kind, read "precedes or equals"; $\leq$ is kept for numbers.

Antisymmetric is not the negation of symmetric. Equality is both, since whenever $a = b$ and $b = a$ , certainly $a = b$ . And " $x + y$ is even" on $ℤ$ is symmetric without being antisymmetric, since it relates $1$ and $3$ both ways. A relation can also be neither: " $x$ divides $y$ " on $ℤ$ relates $2$ to $4$ and not back, so it is not symmetric, and it relates $2$ and $- 2$ both ways, so it is not antisymmetric.

To prove antisymmetry, take arbitrary $a$ and $b$ , assume both $a ⪯ b$ and $b ⪯ a$ , and deduce $a = b$ . To refute it, exhibit two different elements related both ways.

A relation on $A$ that is reflexive, antisymmetric and transitive is a partial order, and $A$ with it is a partially ordered set, or poset, written $(A, ⪯)$ when the relation needs naming. Three examples carry the lesson.

The first is $\leq$ on $ℝ$ , with the ordering facts of school algebra taken as known. Reflexivity is $x \leq x$ . For antisymmetry, suppose $x \leq y$ and $y \leq x$ ; if $x \neq y$ then $x < y$ and $y < x$ , and adding gives $x + y < y + x$ , which is false, so $x = y$ . For transitivity, $x \leq y$ and $y \leq z$ mean $y - x \geq 0$ and $z - y \geq 0$ , and adding gives $z - x \geq 0$ . Every subset of $ℝ$ , such as $ℕ$ , $ℤ$ or $ℚ$ , inherits the order, and more generally a partial order restricted to any subset is still a partial order, since the three properties are universal statements and survive shrinking the domain.

Example. Let $X$ be a set. Prove that $\subseteq$ is a partial order on the power set $P (X)$ .

Reflexive: for every $A \in P (X)$ , every element of $A$ is an element of $A$ , so $A \subseteq A$ . Antisymmetric: let $A \subseteq B$ and $B \subseteq A$ . Each set is a subset of the other, which is exactly the double inclusion that proves two sets equal, so $A = B$ . Transitive: let $A \subseteq B$ and $B \subseteq C$ , and let $x \in A$ . Since $A \subseteq B$ , $x \in B$ , and since $B \subseteq C$ , $x \in C$ . As $x$ was arbitrary, $A \subseteq C$ . All three properties hold, so $\subseteq$ is a partial order on $P (X)$ .

Now you. Prove that divisibility is a partial order on $ℕ$ .

Answer

Reflexive: $a = a \cdot 1$ , so $a ∣ a$ . Transitive: let $a ∣ b$ and $b ∣ c$ , say $b = a k$ and $c = b m$ with $k, m$ integers. Then $c = a (k m)$ and $k m$ is an integer, so $a ∣ c$ . Antisymmetric: let $a ∣ b$ and $b ∣ a$ , say $b = a k$ and $a = b m$ . Then $a = a k m$ , and since $a \neq 0$ , $k m = 1$ . Because $a$ and $b$ are positive, so are $k$ and $m$ , and two positive integers with product $1$ are both $1$ . So $b = a \cdot 1 = a$ .

The positivity is doing real work. On $ℤ$ , divisibility is still reflexive and transitive, but $2 ∣ - 2$ since $- 2 = 2 \cdot (- 1)$ , and $- 2 ∣ 2$ since $2 = (- 2) (- 1)$ , while $2 \neq - 2$ . The broken step is the last: $k m = 1$ also has the integer solution $k = m = - 1$ . So divisibility is not a partial order on $ℤ$ .

Every partial order comes with a twin. If $⪯$ is a partial order on $A$ , so is its reverse, defined by $a ⪰ b$ when $b ⪯ a$ : each of the three properties, read with the letters exchanged, is the same property again. The reverse of $\leq$ is $\geq$ , and the reverse of $\subseteq$ is $\supseteq$ . This is the duality principle: every definition in this lesson has an upside-down version (least for greatest, lower bound for upper bound), and every theorem proved for one version holds for the other, by applying it to the reverse order. So the lesson proves each fact once.

What if a relation is reflexive and transitive but not antisymmetric?

Then it is a preorder, and preorders are common: divisibility on $ℤ$ ; " $| x | \leq | y |$ " on $ℝ$ , which relates $3$ and $- 3$ both ways; "is at least as tall as" on people; and, in the next lesson, "there is an injection from $A$ into $B$ " on sets. A preorder ranks, but it allows ties between different objects.

A preorder always hides a partial order, and the equivalence relations of the previous lesson are what find it. Let $⊑$ be a preorder on $A$ , and say $a \sim b$ when $a ⊑ b$ and $b ⊑ a$ . This is an equivalence relation: reflexive because $a ⊑ a$ , symmetric because its definition is, and transitive because $a ⊑ b ⊑ c$ and $c ⊑ b ⊑ a$ give $a ⊑ c$ and $c ⊑ a$ . On the classes, define $[a] \leq [b]$ when $a ⊑ b$ .

The definition uses representatives, so it must be checked to be well defined, as operations on classes were in the lesson on equivalence relations. Suppose $a \sim a'$ , $b \sim b'$ and $a ⊑ b$ . Then $a' ⊑ a ⊑ b ⊑ b'$ , so $a' ⊑ b'$ by transitivity. The relation on classes is reflexive and transitive because $⊑$ is, and it is antisymmetric: $[a] \leq [b]$ and $[b] \leq [a]$ mean $a ⊑ b$ and $b ⊑ a$ , so $a \sim b$ and $[a] = [b]$ . Collapsing the ties produces a partial order.

For divisibility on $ℤ$ , the ties are $n$ and $- n$ , the classes are ${0}$ and the pairs ${n, - n}$ , and choosing the non-negative member of each gives divisibility on ${0, 1, 2, \dots}$ , a genuine partial order. For injections between sets, the ties are pairs of sets each injecting into the other, and the question of whether a tie means there is a bijection between them is exactly the Schröder and Bernstein theorem, proved in the next lesson.

Total orders and strict orders

Two elements $a$ and $b$ of a poset are comparable when $a ⪯ b$ or $b ⪯ a$ , and incomparable otherwise. A partial order in which every pair is comparable is a total order, or linear order, because its elements line up in a single row. The order $\leq$ on $ℝ$ is total: for any two reals, either $x \leq y$ or $y \leq x$ .

The other two examples are not. Neither of $2$ and $3$ divides the other, so they are incomparable under divisibility, and so are $4$ and $6$ . In $P ({1, 2})$ the sets ${1}$ and ${2}$ are incomparable, since neither is a subset of the other. This is what "partial" means: the order ranks some pairs and is silent about others.

Incomparability is where intuition from numbers misleads. In a total order, "not $a \leq b$ " means " $b < a$ ". In a partial order it does not: $2$ does not divide $3$ , and $3$ does not come before $2$ either. A proof that says " $a ⪯ b$ fails, so $b$ precedes $a$ " has assumed the order is total.

Each partial order has a strict version: $a ≺ b$ means $a ⪯ b$ and $a \neq b$ , which turns $\leq$ into $<$ , $\subseteq$ into "is a proper subset of", and divisibility into "divides and is different from". The strict versions have their own axioms. A relation $≺$ on $A$ is a strict partial order when it is irreflexive (no $a$ has $a ≺ a$ ) and transitive.

Proposition. If $⪯$ is a partial order on $A$ , and $a ≺ b$ means $a ⪯ b$ and $a \neq b$ , then $≺$ is a strict partial order. Moreover it is asymmetric: $a ≺ b$ and $b ≺ a$ never both hold.

Proof. Irreflexive: $a ≺ a$ would require $a \neq a$ . Transitive: let $a ≺ b$ and $b ≺ c$ . Then $a ⪯ b$ and $b ⪯ c$ , so $a ⪯ c$ . If $a = c$ , then $a ⪯ b$ and $b ⪯ a$ , so $a = b$ by antisymmetry, contradicting $a ≺ b$ . So $a \neq c$ and $a ≺ c$ . Asymmetric: if $a ≺ b$ and $b ≺ a$ , transitivity gives $a ≺ a$ , contradicting irreflexivity. $□$

The converse also holds: from a strict partial order $≺$ , the relation " $a ≺ b$ or $a = b$ " is a partial order, and the two constructions undo each other. That is Problem 5. So a partial order and a strict partial order carry the same information, and a text may start from either. In a total order, the strict version satisfies trichotomy: for all $a$ and $b$ , exactly one of $a ≺ b$ , $a = b$ , $b ≺ a$ holds. At least one holds by totality, and at most one by irreflexivity and asymmetry.

Hasse diagrams

A finite poset can be drawn economically, leaving reflexivity and transitivity for the reader to fill in. Say that $b$ covers $a$ when $a ≺ b$ and there is no $c$ with $a ≺ c ≺ b$ . The Hasse diagram, named after the number theorist Helmut Hasse, puts each element as a point, places $b$ higher on the page than $a$ whenever $a ≺ b$ , and draws a line only for covering pairs. No arrowheads are needed, since up is the direction of the order.

Take the eight divisors of $30$ , namely $1, 2, 3, 5, 6, 10, 15, 30$ , under divisibility. The number $1$ is covered by the primes $2$ , $3$ and $5$ . Then $2$ is covered by $6$ and $10$ , $3$ by $6$ and $15$ , and $5$ by $10$ and $15$ . Finally $6$ , $10$ and $15$ are each covered by $30$ . That is twelve lines, drawn as the edges of a cube standing on the corner $1$ , with $30$ at the opposite corner. The poset has nineteen strict pairs in all (for instance $2 ≺ 30$ ), but the other seven follow by climbing.

The divisors of $12$ give a different shape. They are $1, 2, 3, 4, 6, 12$ . Here $1$ is covered by $2$ and $3$ ; $2$ is covered by $4$ and $6$ ; $3$ by $6$ ; and $4$ and $6$ are covered by $12$ . Note that $12$ does not cover $2$ , because $4$ and $6$ lie between. Those seven lines draw two squares sharing an edge, from $2$ to $6$ , rather than a cube.

Hasse diagrams under divisibility. The eight divisors of 30 form a cube with 1 at the bottom, 30 at the top and twelve covering lines. The six divisors of 12 form two squares sharing the edge from 2 to 6 (highlighted), with seven covering lines.

The diagram loses nothing, because in a finite poset the covering pairs determine the whole order.

Proposition. In a finite poset, $a ≺ b$ if and only if there are elements $a = c_{0} ≺ c_{1} ≺ \dots ≺ c_{k} = b$ with $k \geq 1$ in which each $c_{i + 1}$ covers $c_{i}$ .

Proof. ( $\Leftarrow$ ) By transitivity of $≺$ , applied $k - 1$ times, $c_{0} ≺ c_{k}$ .

( $\Rightarrow$ ) Suppose $a ≺ b$ . Consider all sequences $a = c_{0} ≺ c_{1} ≺ \dots ≺ c_{k} = b$ in which each term is strictly below the next. There is at least one, with $k = 1$ . In any such sequence the terms are distinct, since $c_{i} ≺ c_{j}$ for $i < j$ by transitivity, and $≺$ is irreflexive. So $k + 1$ is at most the number of elements of the poset, and among the finitely many possible lengths there is a largest; take a sequence with $k$ as large as possible. If some $c_{i + 1}$ did not cover $c_{i}$ , there would be a $c$ with $c_{i} ≺ c ≺ c_{i + 1}$ , and inserting it would give a longer sequence. So every step is a covering pair. $□$

Finiteness was used, and it is needed. In $(ℚ, \leq)$ no element covers another at all, since between $p < q$ lies $\frac{p + q}{2}$ ; a Hasse diagram of $ℚ$ would be dots and no lines.

The cube is no accident. A divisor of $30$ is a product of some of the primes $2$ , $3$ and $5$ , and $a ∣ b$ exactly when the primes of $a$ are among those of $b$ . The precise word for "the same poset under different names" is this. An order isomorphism from $(A, ⪯)$ to $(B, ⊑)$ is a bijection $f : A \to B$ with $a ⪯ a'$ if and only if $f (a) ⊑ f (a')$ , for all $a, a' \in A$ ; the two posets are then isomorphic. The map sending each divisor of $30$ to its set of prime factors, $1 \mapsto \emptyset$ , $6 \mapsto {2, 3}$ , $30 \mapsto {2, 3, 5}$ and so on, is an order isomorphism onto $(P ({2, 3, 5}), \subseteq)$ , and isomorphic posets have the same Hasse diagram. The "if and only if" matters: the identity map from $({1, 2, 3}, ∣)$ to $({1, 2, 3}, \leq)$ is a bijection that preserves order ( $a ∣ b$ gives $a \leq b$ ), but $2 \leq 3$ while $2$ does not divide $3$ , so it is not an isomorphism.

The divisors of $12$ are $2^{i} 3^{j}$ with $0 \leq i \leq 2$ and $0 \leq j \leq 1$ , and $2^{i} 3^{j} ∣ 2^{i'} 3^{j'}$ exactly when $i \leq i'$ and $j \leq j'$ . The product order on $A \times B$ , for posets $A$ and $B$ , sets $(a, b) ⪯ (a', b')$ when $a ⪯ a'$ in $A$ and $b ⪯ b'$ in $B$ . So the divisors of $12$ are isomorphic to ${0, 1, 2} \times {0, 1}$ in the product order, a three by two grid, which is the two squares of the figure. The product order is a partial order, checked coordinate by coordinate, but it is rarely total: in $ℝ \times ℝ$ , the points $(1, 0)$ and $(0, 1)$ are incomparable.

Maximal against greatest

"Top" has two meanings in a poset, and they come apart as soon as the order is not total. An element $g$ of $A$ is greatest when everything lies below it: $a ⪯ g$ for every $a \in A$ . An element $m$ is maximal when nothing lies strictly above it: there is no $a \in A$ with $m ≺ a$ . By duality, an element $ℓ$ is least when $ℓ ⪯ a$ for every $a \in A$ , and minimal when no $a \in A$ has $a ≺ ℓ$ .

Take the divisors of $12$ other than $12$ , the set ${1, 2, 3, 4, 6}$ under divisibility. Nothing in it is a proper multiple of $4$ or of $6$ , so both are maximal. Neither is greatest, since neither divides the other, and nothing else could be, since a greatest element would be a multiple of both. So there are two maximal elements and no greatest. At the bottom, $1$ divides everything and is least. In a Hasse diagram the maximal elements are the points with no line going up, and the minimal ones the points with no line going down.

Greatest is a statement about every element; maximal is a statement about none. Written out with quantifiers,

g greatest: \forall a \in A (a ⪯ g) m maximal: \neg \exists a \in A (m ≺ a)

and the difference is the difference between " $a ⪯ m$ " and "not $m ≺ a$ ", which the previous section showed are the same only in a total order. A maximal element may simply be incomparable with the rest. In a total order every pair is comparable, and the two notions coincide.

Example. Prove that a poset has at most one greatest element.

Let $g$ and $g'$ both be greatest elements of $A$ . Since $g$ is greatest and $g' \in A$ , we have $g' ⪯ g$ . Since $g'$ is greatest and $g \in A$ , we have $g ⪯ g'$ . By antisymmetry, $g = g'$ .

Antisymmetry supplies the equality, and it is why one may speak of "the greatest element", written $\max A$ when it exists; by duality the least element, $\min A$ , is unique too. In a preorder the argument fails at exactly that step, and "greatest" elements can tie.

Now you. Prove that if a poset $A$ has a greatest element $g$ , then $g$ is the only maximal element of $A$ .

Answer

First, $g$ is maximal. Suppose $g ≺ a$ for some $a \in A$ , so $g ⪯ a$ and $g \neq a$ . Since $g$ is greatest, $a ⪯ g$ , and antisymmetry gives $a = g$ , a contradiction. Second, let $m$ be any maximal element. Since $g$ is greatest, $m ⪯ g$ . If $m \neq g$ then $m ≺ g$ , contradicting maximality of $m$ . So $m = g$ .

The poset ${1, 2, 3, 4, 6}$ is the contrapositive at work: it has two maximal elements, so it cannot have a greatest one. The converse of the Now you, that a unique maximal element must be greatest, is true for finite posets and false for infinite ones; Problem 6 asks for both halves.

Infinite posets can lack maximal and minimal elements altogether: under $\leq$ , $ℕ$ has no maximal element, since $n < n + 1$ , and $ℤ$ has neither kind. Finite posets cannot.

Theorem. Every finite non-empty poset has a minimal element and a maximal element.

Proof. Let $A$ be a finite non-empty poset. For each $x \in A$ , let $d (x)$ be the number of elements $y \in A$ with $y ≺ x$ . The values $d (x)$ form a non-empty set of non-negative integers, so by well-ordering some $x \in A$ has $d (x)$ as small as possible. Suppose, for a contradiction, that some $y \in A$ has $y ≺ x$ . Every $z$ with $z ≺ y$ also has $z ≺ x$ , by transitivity, so the elements strictly below $y$ are among those strictly below $x$ . The element $y$ is itself strictly below $x$ but not strictly below $y$ , since $≺$ is irreflexive. So $d (y) \leq d (x) - 1 < d (x)$ , contradicting the choice of $x$ . Hence $x$ is minimal. Applying this to the reverse order gives a maximal element. $□$

Applied to the set ${y \in A : y ⪯ x}$ , which contains $x$ and so is not empty, the theorem gives more: in a finite poset, every element lies above some minimal element, and dually below some maximal one. The last section of the lesson asks what replaces this theorem when the poset is infinite.

Upper bounds and the least upper bound

Maximal and greatest look inside a set. Bounds look at it from outside, within a larger poset. Let $S$ be a subset of a poset $A$ . An element $u \in A$ is an upper bound of $S$ when $s ⪯ u$ for every $s \in S$ , and $S$ is bounded above when it has one. Lower bounds are defined the other way up. An upper bound need not belong to $S$ : in $ℝ$ , the upper bounds of $[0, 1)$ are exactly the numbers $u \geq 1$ , and none of them is in the set.

Among the upper bounds, the one that matters is the lowest. An element $u$ is the least upper bound, or supremum, of $S$ , written $\sup S$ , when two conditions hold:

(i) s ⪯ u for every s \in S, (ii) u ⪯ v for every upper bound v of S

Condition (i) says $u$ is an upper bound; condition (ii) says it lies below every other one. Together they say $u$ is the least element of the set of upper bounds, so by the upside-down version of the Example above there is at most one, and "the" is earned. The greatest lower bound, or infimum, $\inf S$ , is defined the other way up. A set with a greatest element has that element as its supremum: $\max S$ is an upper bound in $S$ , and every upper bound $v$ of $S$ has $\max S ⪯ v$ because $\max S \in S$ .

The definition works in any poset. Under divisibility on $ℕ$ the upper bounds of ${4, 6}$ are the common multiples, and the section on lattices shows that the least of them in the divisibility order is $12$ , the least common multiple. Under $\subseteq$ , $\sup {A, B} = A \cup B$ , since $A \cup B$ contains both, and any set containing $A$ and $B$ contains their union.

In $ℝ$ , where $\leq$ is total, condition (ii) has a working form: no number below $u$ is an upper bound, that is, for every $b < u$ some $s \in S$ has $s > b$ . (This is (ii) contraposed: " $u \leq v$ for every upper bound $v$ " says that every $v$ with $v < u$ fails to be an upper bound, and in a total order "not $u \leq v$ " is " $v < u$ ".) If $\sup S$ belongs to $S$ , it is the greatest element: $\sup [0, 1] = 1 = \max [0, 1]$ . But it need not belong.

Example. Prove that $S = {1 - \frac{1}{n} : n \in ℕ}$ has $\sup S = 1$ , and that $1 \notin S$ .

The set is ${0, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \dots}$ . For (i), each element satisfies $1 - \frac{1}{n} < 1$ because $\frac{1}{n} > 0$ , so $1$ is an upper bound. For (ii), let $b < 1$ ; we show $b$ is not an upper bound. Since $1 - b > 0$ , choose a natural number $n > \frac{1}{1 - b}$ , which exists because $ℕ$ has no upper bound in $ℝ$ , a fact proved in the lesson on the real numbers. Then $\frac{1}{n} < 1 - b$ , so $1 - \frac{1}{n} > b$ , and an element of $S$ lies above $b$ . Every upper bound is therefore at least $1$ , and $\sup S = 1$ . Finally $1 - \frac{1}{n} = 1$ would force $\frac{1}{n} = 0$ , which no $n$ allows, so $1 \notin S$ , and $S$ has a supremum but no greatest element. Its infimum is $0$ , which is its least element.

Now you. Prove that $\sup (0, 1) = 1$ and $\inf (0, 1) = 0$ without using any fact about $ℕ$ .

Answer

Supremum. For (i), every $x \in (0, 1)$ satisfies $x < 1$ , so $1$ is an upper bound. For (ii), let $b < 1$ and find an element of $(0, 1)$ above it. If $b \leq 0$ , the element $\frac{1}{2}$ will do. If $0 < b < 1$ , take the midpoint $x = \frac{b + 1}{2}$ : then $b < x < 1$ and $x > 0$ , so $x \in (0, 1)$ and $x > b$ . So no number below $1$ is an upper bound, and $\sup (0, 1) = 1$ , which is not in the interval.

Infimum. Every $x \in (0, 1)$ has $x > 0$ , so $0$ is a lower bound. Let $b > 0$ . If $b \geq 1$ , the element $\frac{1}{2}$ lies below it. If $0 < b < 1$ , then $x = \frac{b}{2}$ satisfies $0 < x < b < 1$ , so $x \in (0, 1)$ and $x < b$ . So no number above $0$ is a lower bound, and $\inf (0, 1) = 0$ .

A supremum can fail to exist in two ways: there may be no upper bounds at all, as for $ℕ$ in $ℝ$ , or there may be upper bounds and no least one. The first failure is familiar; the second is subtler, and the next paragraphs and the section on lattices both show it.

What is the supremum of the empty set?

Condition (i) for $S = \emptyset$ says " $s ⪯ u$ for every $s \in \emptyset$ ", a universal statement over an empty domain, so it is vacuously true: every element of the poset is an upper bound of $\emptyset$ . Condition (ii) then asks for an element below every element of the poset. So $\sup \emptyset$ exists exactly when the poset has a least element, and then it is that element. Dually, $\inf \emptyset$ is the greatest element, if there is one.

In $(P (X), \subseteq)$ that gives $\sup \emptyset = \emptyset$ and $\inf \emptyset = X$ . The second looks odd until it is read as an intersection: the intersection of no sets at all is the set of $x$ that belong to every set in an empty family, and every $x \in X$ passes that test vacuously. In $ℝ$ , which has no least element, $\emptyset$ has no supremum; that is why the completeness axiom of the lesson on the real numbers speaks only of non-empty sets.

The power set is better behaved than $ℝ$ in every respect: every family of subsets of $X$ , of any size, has a supremum, its union, and an infimum, its intersection. The proof is the one for two sets. The union of a family contains each member, and any set containing each member contains every element of the union. A poset in which every subset has a supremum and an infimum is a complete lattice, and complete lattices have a remarkable property: every order-preserving map from one to itself has a fixed point. Problem 13 proves this for power sets, and the result gives a second proof of the Schröder and Bernstein theorem of the next lesson.

Whether a least upper bound exists depends on the poset the bounds are drawn from, just as surjectivity depended on the codomain. Work in $ℚ$ under $\leq$ , and let

T = {q \in ℚ : q^{2} < 2}

The set is non-empty, since $1 \in T$ , and bounded above in $ℚ$ by $2$ , since a rational $q > 2$ has $q^{2} > 4$ . In fact any positive rational $u$ with $u^{2} > 2$ is an upper bound: if some $q \in T$ had $q > u$ , then $q > 0$ and $q^{2} > u^{2} > 2$ , contradicting $q \in T$ .

So the rational upper bounds can be pushed down, and the elements of $T$ pushed up. The decimals $1.5$ , $1.42$ , $1.415$ and $1.4143$ have squares $2.25$ , $2.0164$ , $2.002225$ and $2.00024449$ , all above $2$ , so each is an upper bound. The decimals $1.4$ , $1.41$ , $1.414$ and $1.4142$ have squares $1.96$ , $1.9881$ , $1.999396$ and $1.99996164$ , all below $2$ , so each is in $T$ . The two sides close in on a number whose square is $2$ , and no rational has square $2$ .

That suggests a fact, stated here and proved in the lesson on the real numbers: $T$ is non-empty and bounded above in $ℚ$ , yet has no least upper bound in $ℚ$ , because below every rational upper bound lies a smaller one. Inside $ℝ$ the same set has supremum $\sqrt{2}$ . The rationals are totally ordered, as the reals are, yet something the reals have is missing from them, and least upper bounds are where the absence shows.

Lattices, and divisibility as one

The suprema of two-element sets deserve names. In a poset, the join of $a$ and $b$ , written $a \lor b$ , is $\sup {a, b}$ , and their meet, written $a \land b$ , is $\inf {a, b}$ , whenever these exist. A lattice is a poset in which every two elements have a join and a meet. (The symbols are the logical "or" and "and", and the resemblance is deliberate: in $P (X)$ , $x \in A \lor B$ exactly when $x \in A$ or $x \in B$ .)

Three lattices are already in view. In a total order, $a \lor b = \max {a, b}$ and $a \land b = \min {a, b}$ : the two elements are comparable, so one of them is the greatest element of ${a, b}$ and hence its supremum, and dually. In $(P (X), \subseteq)$ , $A \lor B = A \cup B$ and $A \land B = A \cap B$ . The third is divisibility on $ℕ$ , whose meet is the greatest common divisor, and the proof that it exists rests on the well-ordering principle and the division algorithm, as the lemma behind Euclid's lemma did in the lesson on contrapositive and contradiction.

Example. Let $a, b \in ℕ$ . Prove that ${a, b}$ has an infimum in $(ℕ, ∣)$ , and that it can be written as $a x + b y$ for some integers $x$ and $y$ .

Let $S$ be the set of positive integers of the form $a x + b y$ with $x, y \in ℤ$ . It is not empty, since $a = a \cdot 1 + b \cdot 0$ is in it. By the well-ordering principle it has a least element $d$ , and $d = a x_{0} + b y_{0}$ for some integers $x_{0}$ and $y_{0}$ .

First, $d$ is a lower bound, that is, $d ∣ a$ and $d ∣ b$ . By the division algorithm, $a = d q + r$ with $0 \leq r < d$ . Then

r = a - d q = a - (a x_{0} + b y_{0}) q = a (1 - q x_{0}) + b (- q y_{0})

has the form $a x + b y$ . If $r$ were positive it would belong to $S$ and be smaller than $d$ , contradicting the choice of $d$ . So $r = 0$ and $d ∣ a$ . The same argument with $b$ in place of $a$ gives $d ∣ b$ .

Second, $d$ lies above every lower bound. Let $c \in ℕ$ with $c ∣ a$ and $c ∣ b$ . A common divisor of two integers divides every integer combination of them, so $c ∣ a x_{0} + b y_{0} = d$ .

So $d$ is a lower bound lying above every lower bound: $d = \inf {a, b} = a \land b$ , and $d = a x_{0} + b y_{0}$ . For $a = 12$ and $b = 18$ , the positive combinations include $12$ , $18$ , $18 - 12 = 6$ , and nothing smaller, since every combination $12 x + 18 y = 6 (2 x + 3 y)$ is a multiple of $6$ . So $12 \land 18 = 6 = 12 \cdot (- 1) + 18 \cdot 1$ .

The infimum under divisibility is the greatest common divisor, $\gcd (a, b)$ , and here "greatest" has two meanings that happen to agree: $d$ is greatest in the divisibility order, and since every common divisor $c$ divides $d > 0$ , also $c \leq d$ , so $d$ is greatest in size. The representation $d = a x_{0} + b y_{0}$ is Bézout's identity, and the Discrete Mathematics lesson on divisibility computes $x_{0}$ and $y_{0}$ with Euclid's algorithm.

Now you. Let $a, b \in ℕ$ , and let $m$ be the least positive common multiple of $a$ and $b$ (it exists because $a b$ is one). Prove that $m = \sup {a, b}$ in $(ℕ, ∣)$ .

Answer

The set of positive common multiples of $a$ and $b$ contains $a b$ , so by well-ordering it has a least element $m$ . Since $a ∣ m$ and $b ∣ m$ , $m$ is an upper bound of ${a, b}$ .

Let $n \in ℕ$ be any upper bound, so $a ∣ n$ and $b ∣ n$ . By the division algorithm, $n = m q + r$ with $0 \leq r < m$ . Since $a$ divides both $n$ and $m$ , it divides $r = n - m q$ , and likewise $b ∣ r$ . If $r$ were positive, it would be a positive common multiple smaller than $m$ , contradicting the choice of $m$ . So $r = 0$ and $m ∣ n$ . Hence $m$ lies below every upper bound, and $m = \sup {a, b} = a \lor b$ , the least common multiple.

So $(ℕ, ∣)$ is a lattice, with least element $1$ and no greatest element. It becomes more symmetric if $0$ is admitted: on ${0, 1, 2, \dots}$ divisibility is still a partial order (antisymmetry needs a line for $0$ , since $0 ∣ b$ forces $b = 0$ ), and $0$ is its greatest element, because $n ∣ 0$ for every $n$ . The divisors of a fixed number $n$ form a lattice as well, since the gcd and lcm of two divisors of $n$ are again divisors of $n$ (the lcm because $n$ is a common multiple, and so a multiple of the least one). The cube and the two squares in the figure are lattices of this kind.

A subset of a lattice need not be a lattice, and the join inside a subset can differ from the join outside it. In ${1, 2, 3, 4, 6}$ under divisibility, $4$ and $6$ have no upper bound at all, so there is no join. In ${1, 2, 3, 12, 18}$ , the set ${2, 3}$ has two upper bounds, $12$ and $18$ , which are incomparable, so it has upper bounds and no least one: the second way a supremum can fail. And ${1, 2, 3, 5, 30}$ is a lattice in which $2 \lor 3 = 30$ , since $6$ is not there; inside $ℕ$ the join is $6$ . Suprema are taken in a named poset, and changing the poset changes the answer, exactly as $T$ had a supremum in $ℝ$ and none in $ℚ$ . Some laws, on the other hand, hold in every lattice, and Problem 9 proves two of them.

Well-orders

The well-ordering principle says something about $(ℕ, \leq)$ that is false for $ℤ$ , for the non-negative rationals and for $[0, 1]$ : every non-empty subset has a least element. That property gets its own name. A total order $⪯$ on $W$ is a well-order when every non-empty subset of $W$ has a least element, and $(W, ⪯)$ is then well-ordered.

So $ℕ$ is well-ordered by $\leq$ , and so is every finite totally ordered set, since by the theorem on finite posets a non-empty finite subset has a minimal element, and in a total order a minimal element is least. The set $ℤ$ is not, and neither is ${\frac{1}{n} : n \in ℕ}$ under $\leq$ , which has no least element. Totality is almost free in the definition: if a partial order has a least element in every non-empty subset, then for any $a$ and $b$ the subset ${a, b}$ has a least element, which makes $a$ and $b$ comparable.

Well-orders are exactly the orders along which one cannot descend for ever.

Proposition. In a well-ordered set $W$ there is no infinite sequence $x_{1} ≻ x_{2} ≻ x_{3} ≻ \dots$ with each term strictly below the one before.

Proof. Suppose there were such a sequence. Its set of values ${x_{n} : n \in ℕ}$ is a non-empty subset of $W$ , so it has a least element, say $x_{k}$ . But $x_{k + 1}$ is also in the set and $x_{k + 1} ≺ x_{k}$ , a contradiction. $□$

The converse holds for total orders too: if some non-empty $S \subseteq W$ has no least element, choose $x_{1} \in S$ ; it is not least, so, by totality, some $x_{2} \in S$ has $x_{2} ≺ x_{1}$ ; that is not least either, so some $x_{3} \in S$ has $x_{3} ≺ x_{2}$ ; and so on for ever. The argument makes infinitely many choices one after another, a point that returns at the end of the lesson.

The reason to care about well-orders is that induction works along them. Strong induction, from the induction lesson, is the case $W = ℕ$ of this theorem.

Theorem (induction over a well-order). Let $(W, ⪯)$ be well-ordered and let $P (x)$ be a statement about elements of $W$ . Suppose that for every $x \in W$ , if $P (y)$ holds for all $y ≺ x$ , then $P (x)$ holds. Then $P (x)$ holds for every $x \in W$ .

Proof. Suppose not. Then the set of counterexamples ${x \in W : P (x) is false}$ is non-empty, so it has a least element $x_{0}$ . Every $y ≺ x_{0}$ is smaller than the least counterexample, so $P (y)$ holds. By the hypothesis, $P (x_{0})$ holds, a contradiction. $□$

There is no separate base case, because for the least element of $W$ the condition " $P (y)$ for all $y ≺ x$ " is vacuous, and the hypothesis must prove $P$ outright there.

The lexicographic order

A dictionary orders words by their first letter, breaks ties by the second, and so on. For totally ordered sets $A$ and $B$ , the lexicographic order on $A \times B$ does the same with pairs:

(a, b) ≺ (a', b') ⟺ a ≺ a' or (a = a' and b ≺ b')

with $(a, b) ⪯ (a', b')$ meaning $(a, b) ≺ (a', b')$ or $(a, b) = (a', b')$ . On $ℕ \times ℕ$ it runs

(1, 1) ≺ (1, 2) ≺ (1, 3) ≺ \dots ≺ (2, 1) ≺ (2, 2) ≺ \dots ≺ (3, 1) ≺ \dots

Every pair $(1, n)$ comes before $(2, 1)$ , so $(2, 1)$ has infinitely many predecessors, and the order is not isomorphic to $(ℕ, \leq)$ , in which every element has finitely many. The lexicographic order is total: given $(a, b) \neq (a', b')$ , either $a \neq a'$ , and the pair with the smaller first coordinate comes first, or $a = a'$ and $b \neq b'$ , and the smaller second coordinate decides. That $⪯$ is a partial order follows from Problem 5 once the strict relation $≺$ is shown to be irreflexive and transitive, which is Problem 1.

Example. Prove that the lexicographic order on $ℕ \times ℕ$ is a well-order.

Let $S$ be a non-empty subset of $ℕ \times ℕ$ . The set of first coordinates $F = {a : (a, b) \in S for some b}$ is a non-empty subset of $ℕ$ , so it has a least element $a_{0}$ . The set $G = {b : (a_{0}, b) \in S}$ is non-empty, since $a_{0} \in F$ , so it has a least element $b_{0}$ , and $(a_{0}, b_{0}) \in S$ .

We show $(a_{0}, b_{0}) ⪯ (a, b)$ for every $(a, b) \in S$ . Since $a \in F$ , $a_{0} \leq a$ . If $a_{0} < a$ , then $(a_{0}, b_{0}) ≺ (a, b)$ by the first clause of the definition. If $a_{0} = a$ , then $b \in G$ , so $b_{0} \leq b$ , and either $b_{0} = b$ , when the pairs are equal, or $b_{0} < b$ , when $(a_{0}, b_{0}) ≺ (a, b)$ by the second clause. So $(a_{0}, b_{0})$ is the least element of $S$ .

The proof used well-ordering twice, once per coordinate, and the same proof shows that the lexicographic product of any two well-orders is a well-order.

Now you. Order $ℕ$ by putting every even number before every odd number, and each parity in its usual order: $m ⊑ n$ when $m$ and $n$ have the same parity and $m \leq n$ , or $m$ is even and $n$ is odd. So $2 ⊏ 4 ⊏ 6 ⊏ \dots ⊏ 1 ⊏ 3 ⊏ \dots$ . Given that $⊑$ is a total order, prove that it is a well-order, and name an element with infinitely many predecessors.

Answer

Let $S$ be a non-empty subset of $ℕ$ . If $S$ contains an even number, let $e$ be the least even element of $S$ in the usual order, which exists by well-ordering of $ℕ$ applied to the even elements of $S$ . For $n \in S$ : if $n$ is odd, $e ⊑ n$ because evens precede odds; if $n$ is even, $e \leq n$ by the choice of $e$ , so $e ⊑ n$ . So $e$ is least. If $S$ contains no even number, every element is odd, and the least element of $S$ in the usual order, $o$ , satisfies $o \leq n$ for every $n \in S$ , all of the same parity, so $o ⊑ n$ . In both cases $S$ has a least element.

The number $1$ has infinitely many predecessors, every even number. As with $(2, 1)$ in $ℕ \times ℕ$ , that shows the order is not isomorphic to $(ℕ, \leq)$ .

The lexicographic order on finite words is where intuition fails. Order words in the letters $a$ and $b$ as a dictionary does, with a word placed before its own extensions. Then

b ≻ a b ≻ a a b ≻ a a a b ≻ \dots

an infinite descending sequence, so by the Proposition the dictionary order on words is not a well-order, even though it is total. The pairs were safe because they have fixed length. The repair for words is shortlex: compare lengths first, and use the dictionary only between words of the same length. There are finitely many words of each length, so shortlex lists all words in one sequence, $a, b, a a, a b, b a, b b, a a a, \dots$ , and it is a well-order.

Lexicographic orders are the standard tool for proving that a process stops. If each step of an algorithm replaces a pair of natural numbers by a lexicographically smaller one, the algorithm must halt, since otherwise its pairs form an infinite descending sequence. That remains true when a step may lower the first coordinate and then raise the second coordinate as much as it likes: $(3, 1)$ may be followed by $(2, 1 000 000)$ , and still the run is finite.

What does a well-order longer than

ℕ

look like, and why would anyone want one?

The two orders met above, evens before odds and the lexicographic order on $ℕ \times ℕ$ , are well-orders that continue past a complete copy of $ℕ$ . Cantor, in his papers of 1883, counted along such orders with ordinal numbers: $ω$ for the order type of $ℕ$ , $ω + 1$ for $ℕ$ followed by one more element, $ω + ω = ω \cdot 2$ for evens before odds, and $ω \cdot ω = ω^{2}$ for $ℕ \times ℕ$ in lexicographic order, which is $ω$ copies of $ω$ in a row. Every well-ordered set is isomorphic to exactly one ordinal, and the ordinals are themselves well-ordered, so they measure the length of a well-order as the natural numbers measure the size of a finite set.

The practical use is induction and termination beyond the reach of $ℕ$ . Wilhelm Ackermann defined in 1928 a function on pairs of non-negative integers by

A (0, n) = n + 1, A (m + 1, 0) = A (m, 1), A (m + 1, n + 1) = A (m, A (m + 1, n))

It is not obvious that this defines anything: the last clause feeds a value of $A$ back into $A$ . Induction over the lexicographic well-order settles it. Suppose $A$ is defined at every pair lexicographically below $(m, n)$ . If $m = 0$ , the first clause defines $A (0, n)$ outright. The second clause refers to $(m - 1, 1)$ , whose first coordinate is smaller. The third first refers to $(m, n - 1)$ , which is smaller, so $A (m, n - 1)$ is some number $k$ ; it then refers to $(m - 1, k)$ , which is smaller whatever $k$ is, because the first coordinate dropped. So $A (m, n)$ is defined, and by the theorem it is defined everywhere. No induction on a single natural number does this directly, because the second coordinate can jump arbitrarily high. The function grows explosively: $A (4, 2) = 2^{65536} - 3$ , a number of $19 729$ decimal digits.

Chains and antichains

Inside any poset there are two extreme kinds of subset. A chain is a subset in which every two elements are comparable, so that the order restricted to it is total. An antichain is a subset in which no two distinct elements are comparable. In $(ℕ, ∣)$ the powers of $3$ form a chain, $1 ∣ 3 ∣ 9 ∣ 27 ∣ \dots$ , and the primes form an antichain, since no prime divides a different prime. In $(P (X), \subseteq)$ the one-element subsets form an antichain. A single element is both a chain and an antichain, and so is $\emptyset$ .

For a finite poset, the height is the largest number of elements in a chain and the width the largest number of elements in an antichain. The two interact through one simple fact.

Lemma. A chain and an antichain have at most one element in common.

Proof. If $x \neq y$ were both in the chain $C$ and the antichain $D$ , they would be comparable because $C$ is a chain and incomparable because $D$ is an antichain. $□$

So if a poset is the union of $k$ chains, every antichain has at most $k$ elements: each of its elements lies in one of the chains, and no chain can hold two of them, so the pigeonhole principle allows at most $k$ . Dually, if a poset is the union of $k$ antichains, every chain has at most $k$ elements. Covers of one kind bound sets of the other kind, and when a cover and a set of the same size can both be found, the height or width is settled. The next theorem says that for chains and height, the bound is always attained.

Theorem (Mirsky). Let $A$ be a finite poset whose largest chain has $h$ elements. Then $A$ is the union of $h$ disjoint antichains.

Proof. For $x \in A$ , let $ℓ (x)$ be the largest number of elements in a chain whose greatest element is $x$ . The chain ${x}$ shows $ℓ (x) \geq 1$ , and $ℓ (x) \leq h$ by the choice of $h$ . For $1 \leq i \leq h$ , let $A_{i} = {x \in A : ℓ (x) = i}$ . Every element lies in exactly one $A_{i}$ .

Each $A_{i}$ is an antichain. Suppose $x ≺ y$ . Take a chain of $ℓ (x)$ elements with greatest element $x$ . Every element of it is $⪯ x$ , hence $≺ y$ , so adding $y$ gives a chain of $ℓ (x) + 1$ elements with greatest element $y$ . Therefore $ℓ (y) \geq ℓ (x) + 1 > ℓ (x)$ . So two comparable distinct elements never share a value of $ℓ$ , and no $A_{i}$ contains two comparable elements. $□$

Leon Mirsky published the theorem in 1971. By the remark before it, no partition into fewer than $h$ antichains is possible, since the chain of $h$ elements would need $h$ different antichains; so the height equals the least number of antichains that cover the poset. Since each antichain has at most $w$ elements, where $w$ is the width, a finite poset of height $h$ and width $w$ has at most $h w$ elements.

The theorem has a practical reading. If $x ≺ y$ means that task $x$ must be finished before task $y$ starts, an antichain is a set of tasks that can run at the same time, and the proof schedules the whole project in $h$ rounds, round $i$ being $A_{i}$ , where $h$ is the length of the longest chain of dependencies. No schedule can use fewer.

Example. Find the height and the width of ${1, 2, \dots, 12}$ under divisibility, and a partition into antichains of the least possible number.

Height. The chain $1 ∣ 2 ∣ 4 ∣ 8$ has four elements. No chain has five: list a chain's elements in increasing order as $c_{1} ∣ c_{2} ∣ \dots$ ; each is a proper multiple of the one before, so at least twice it, and five elements would give $c_{5} \geq 2^{4} c_{1} \geq 16 > 12$ . So the height is $4$ .

Mirsky's partition. The value $ℓ (n)$ is the number of elements in the longest divisor chain ending at $n$ . It is $1$ for $n = 1$ ; $2$ for the primes $2, 3, 5, 7, 11$ (only $1$ lies below them); $3$ for $4, 6, 9, 10$ (for instance $1 ∣ 3 ∣ 9$ , and nothing longer, since the only divisors of $9$ are $1$ , $3$ , $9$ ); and $4$ for $8$ and $12$ (as $1 ∣ 2 ∣ 4 ∣ 8$ and $1 ∣ 2 ∣ 4 ∣ 12$ ). So the antichains are

{1}, {2, 3, 5, 7, 11}, {4, 6, 9, 10}, {8, 12}

and a direct check confirms that no number in any of them divides another in the same set.

Width. The six numbers $7, 8, 9, 10, 11, 12$ form an antichain: a proper multiple of any of them is at least $14$ . And six chains cover the whole poset:

{1, 2, 4, 8}, {3, 6, 12}, {5, 10}, {7}, {9}, {11}

so by the lemma no antichain has more than six elements. The width is $6$ , and $4 \times 6 = 24 \geq 12$ , as it must be.

Now you. Find the height and width of $(P ({1, 2, 3}), \subseteq)$ , the Mirsky partition into antichains, and a cover by chains that proves the width.

Answer

Height. If $S \subseteq T$ and $S \neq T$ , then $T$ has more elements than $S$ . So the sets in a chain have different sizes, and sizes run from $0$ to $3$ , which allows at most four sets. The chain $\emptyset \subseteq {1} \subseteq {1, 2} \subseteq {1, 2, 3}$ has four, so the height is $4$ .

Partition. A longest chain ending at a set $S$ with $k$ elements can include one set of each size from $0$ to $k$ (remove the elements of $S$ one at a time), and no more, by the size argument. So $ℓ (S) = | S | + 1$ , and the antichains are the sets of each size: ${\emptyset}$ , the three singletons, the three pairs, and ${{1, 2, 3}}$ .

Width. The three singletons form an antichain. The three chains

{\emptyset, {1}, {1, 2}, {1, 2, 3}}, {{2}, {2, 3}}, {{3}, {1, 3}}

cover all eight subsets, so no antichain has more than three elements. The width is $3$ .

Is there a theorem with chains and antichains the other way round?

Yes, and it is harder. Mirsky's theorem covers a poset by as few antichains as its height demands. The dual statement covers it by as few chains as its width demands.

Dilworth's theorem. A finite poset whose largest antichain has $w$ elements is the union of $w$ chains.

Robert Dilworth proved it in 1950, twenty-one years before Mirsky's dual, and the delay reflects the difficulty. The easy half, that at least $w$ chains are needed, is the lemma above. The hard half has no neat labelling like $ℓ (x)$ ; the standard proofs go by induction on the size of the poset, splitting at a largest antichain, or deduce it from results on matchings in graphs, and they belong to a course in combinatorics.

Both theorems give the bound $| A | \leq h w$ , and that bound alone has a famous consequence. Paul Erdős and George Szekeres proved in 1935 that every sequence of more than $r s$ distinct real numbers contains an increasing subsequence of more than $r$ terms or a decreasing one of more than $s$ terms. For instance, any ten distinct numbers in a row contain four in increasing order or four in decreasing order. The proof is a choice of partial order, and it is Problem 12.

For power sets the width is known exactly. Emanuel Sperner proved in 1928 that the largest antichain in $P ({1, 2, \dots, n})$ has $(\binom{n}{⌊ n / 2 ⌋})$ elements, the number of subsets of the middle size, so the Now you's answer of $3 = (\binom{3}{1})$ is the case $n = 3$ .

Linear extensions and Zorn's lemma

A partial order can always be completed to a total one without contradicting it. A linear extension of a partial order $⪯$ on $A$ is a total order $\leq^{*}$ on $A$ such that $a ⪯ b$ implies $a \leq^{*} b$ . Listing a degree's modules in an order that respects every prerequisite is finding a linear extension, and so is the "topological sort" a build system performs before compiling files that depend on one another. For the divisors of $12$ , the usual order of size is one linear extension, and $1, 3, 2, 6, 4, 12$ is another.

Theorem. Every partial order on a finite set has a linear extension.

Proof. By induction on the number $n$ of elements. A set with $0$ or $1$ elements is already totally ordered. Let $n \geq 1$ , suppose the claim holds for every set of $n$ elements, and let $(A, ⪯)$ be a poset with $n + 1$ elements. By the theorem on finite posets it has a minimal element $m$ . The set $A ∖ {m}$ has $n$ elements and, with $⪯$ restricted to it, is a poset, so by hypothesis it has a linear extension $\leq'$ . Define $\leq^{*}$ on $A$ by putting $m$ first: $m \leq^{*} x$ for every $x \in A$ , and for $x, y \neq m$ , $x \leq^{*} y$ when $x \leq' y$ . This is a total order, since it is $\leq'$ with one new element placed below everything. It extends $⪯$ : let $x ⪯ y$ . If $x = m$ , then $m \leq^{*} y$ . If $y = m$ , then $x ⪯ m$ , and $x ≺ m$ is impossible because $m$ is minimal, so $x = m$ and $m \leq^{*} m$ . If neither is $m$ , then $x \leq' y$ , so $x \leq^{*} y$ . $□$

For an infinite set, peeling off a minimal element fails: there may be none, and even when there is, the peeling may never reach some elements. A different construction is needed, and it starts with a lemma that orders a single incomparable pair.

Lemma. Let $R$ be a partial order on $A$ , written $x R y$ , and let $a$ and $b$ be incomparable under $R$ . Then

R' = R \cup {(x, y) : x R a and b R y}

is a partial order on $A$ that contains $R$ and has $a R' b$ .

Proof. Call the pairs of $R$ old and the other pairs of $R'$ new. The pair $(a, b)$ is new, since $a R a$ and $b R b$ . $R'$ is reflexive because $R$ is.

Antisymmetric. Let $x R' y$ and $y R' x$ . If both pairs are old, $x = y$ by antisymmetry of $R$ . If $(x, y)$ is old and $(y, x)$ new, then $y R a$ and $b R x$ , so $b R x R y R a$ and, by transitivity, $b R a$ , contradicting incomparability. The case with $(x, y)$ new and $(y, x)$ old is the same with the letters exchanged. If both are new, then $x R a$ and $b R x$ , so $b R a$ , again impossible. So only the first case occurs, and $x = y$ .

Transitive. Let $x R' y$ and $y R' z$ . If both are old, $x R z$ . If $(x, y)$ is old and $(y, z)$ new, then $x R y R a$ and $b R z$ , so $(x, z)$ is new, and in $R'$ . If $(x, y)$ is new and $(y, z)$ old, then $x R a$ and $b R y R z$ , so $(x, z)$ is new. If both are new, then $b R y$ and $y R a$ , so $b R a$ , impossible. In every possible case $x R' z$ . $□$

The lemma fixes one incomparable pair; an infinite set can have infinitely many, and fixing them one at a time is a process with no last step. What replaces "and so on" is a principle about posets.

Zorn's lemma. Let $P$ be a non-empty poset in which every non-empty chain has an upper bound in $P$ . Then $P$ has a maximal element.

It is not proved in this course. It is equivalent, given the other axioms of set theory, to the axiom of choice, which says that from any family of non-empty sets one element can be chosen from each at once; mathematicians take one of the equivalent forms as an axiom. For a finite poset, Zorn's lemma is the theorem on finite posets proved above, which needs no chain condition at all. For infinite posets the hypothesis is essential: in $(ℕ, \leq)$ every element is part of the chain $ℕ$ , which has no upper bound, and there is no maximal element.

Theorem (Szpilrajn). Every partial order on any set has a linear extension.

Proof. Let $⪯$ be a partial order on $A$ , and let $P$ be the set of all partial orders on $A$ that contain $⪯$ , each regarded as a set of pairs, and ordered by $\subseteq$ . $P$ is not empty, since $⪯$ belongs to it.

Let $C$ be a non-empty chain in $P$ , and let $U$ be the union of its members. We show $U \in P$ ; it is then an upper bound of $C$ . $U$ contains $⪯$ , since every member of $C$ does, and it is reflexive for the same reason. For transitivity, let $(x, y)$ and $(y, z)$ be in $U$ , say $(x, y) \in R_{1}$ and $(y, z) \in R_{2}$ with $R_{1}, R_{2} \in C$ . Since $C$ is a chain, one contains the other, say $R_{1} \subseteq R_{2}$ . Then both pairs are in the partial order $R_{2}$ , so $(x, z) \in R_{2} \subseteq U$ . Antisymmetry is proved the same way: if $(x, y)$ and $(y, x)$ are in $U$ , both lie in the larger of the two orders containing them, so $x = y$ .

By Zorn's lemma, $P$ has a maximal element $R$ . Suppose $R$ were not total, with $a$ and $b$ incomparable. The Lemma gives a partial order $R'$ containing $R$ , hence containing $⪯$ , so $R' \in P$ ; and $(a, b) \in R'$ while $(a, b) \notin R$ , so $R \subseteq R'$ and $R \neq R'$ , which would contradict the maximality of $R$ . Hence $R$ is total, and it is a linear extension of $⪯$ . $□$

Edward Szpilrajn published the theorem in 1930. The proof shows the pattern of almost every use of Zorn's lemma. Collect the partial objects, here partial orders extending the given one, and order them by inclusion. Check that the union of a chain of partial objects is again a partial object; the check is usually routine, and it is the step that must not be skipped. Take a maximal partial object, and show that if it were not complete it could be enlarged, usually by a lemma like the one above. The same pattern proves that every vector space has a basis (the partial objects are linearly independent sets, and a maximal one spans), including vector spaces far beyond those of a first linear algebra course, such as $ℝ$ regarded as a vector space over $ℚ$ . It also proves that every connected graph, however infinite, has a spanning tree.

The chain condition is where proofs fail. Let $P$ be the set of finite subsets of $ℕ$ , ordered by $\subseteq$ . The chain ${1} \subseteq {1, 2} \subseteq {1, 2, 3} \subseteq \dots$ has union $ℕ$ , which is not in $P$ , and no finite set contains every member of the chain, so the chain has no upper bound in $P$ . And $P$ has no maximal element: $\emptyset$ lies strictly below ${1}$ , and a non-empty finite set $F$ lies strictly below $F \cup {\max F + 1}$ . Zorn's lemma promises nothing here, and nothing is there.

Why is Zorn's lemma an axiom rather than a theorem?

Because it cannot be proved from the other axioms of set theory, and neither can its negation. Kurt Gödel showed in 1938 that the axiom of choice is consistent with the other axioms of Zermelo and Fraenkel's system, ZF, and Paul Cohen showed in 1963 that its negation is consistent with them too. Since Zorn's lemma and the axiom of choice imply each other over ZF, the same holds for Zorn.

The heuristic argument for Zorn's lemma shows where choice enters. Start anywhere in $P$ . If the current element is not maximal, choose something strictly above it. Continue: after infinitely many steps the elements chosen form a chain, which has an upper bound, so choose one and keep climbing. The climb runs along a well-order that may be far longer than $ℕ$ , but the chosen elements are all different, so it cannot run longer than the size of $P$ allows; it must stop, and it can only stop at a maximal element. Making this rigorous needs the ordinals and a single act of choosing, all at once, a successor for every non-maximal element; the axiom of choice is exactly the licence for that.

Three equivalent forms are usually met together: the axiom of choice, which Ernst Zermelo made explicit in 1904; Zermelo's well-ordering theorem, proved from choice in the same paper, that every set, $ℝ$ included, can be well-ordered; and Zorn's lemma, found by Kazimierz Kuratowski in 1922 and independently by Max Zorn, who published it in 1935. The mathematician Jerry Bona summed up how differently they strike the intuition: the axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma? They are one principle in three costumes.

Choice has strange consequences. Nobody can write down a well-order of $ℝ$ , although one exists if choice is assumed, and the Banach and Tarski paradox of 1924 cuts a solid ball into finitely many pieces that can be moved rigidly and reassembled into two balls the size of the first. Most mathematicians accept choice anyway, because without it much of algebra and analysis breaks, and results proved with it are marked in careful texts when the use is essential.

Zorn's lemma is a statement about infinite sets, and so is the preorder "there is an injection from $A$ into $B$ " met near the start of the lesson. The next lesson takes up that preorder, compares the sizes of infinite sets by functions alone, and asks how many real numbers there are.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Let $A$ and $B$ be totally ordered sets, and let $≺$ be the strict lexicographic order on $A \times B$ . Prove that $≺$ is irreflexive and transitive.

Solution

Write $<$ for the strict orders of $A$ and of $B$ ; both are irreflexive and transitive.

Irreflexive. $(a, b) ≺ (a, b)$ would require $a < a$ , or $a = a$ and $b < b$ . Both are impossible, since $<$ is irreflexive in $A$ and in $B$ .

Transitive. Let $(a, b) ≺ (a', b')$ and $(a', b') ≺ (a ′′, b ′′)$ . There are four cases, according to which clause of the definition gives each relation.

If $a < a'$ and $a' < a ′′$ , then $a < a ′′$ by transitivity in $A$ . If $a < a'$ and $a' = a ′′$ , then $a < a ′′$ . If $a = a'$ and $a' < a ′′$ , then $a < a ′′$ . In these three cases $(a, b) ≺ (a ′′, b ′′)$ by the first clause. If $a = a' = a ′′$ with $b < b'$ and $b' < b ′′$ , then $b < b ′′$ by transitivity in $B$ , and $(a, b) ≺ (a ′′, b ′′)$ by the second clause.

By Problem 5, the relation " $≺$ or $=$ " is therefore a partial order, and the lesson showed it is total.

2. List the covering pairs of the divisors of $36$ under divisibility, and say how many lines the Hasse diagram has. Find the height and the width, with proof.

Solution

The divisors are $1, 2, 3, 4, 6, 9, 12, 18, 36$ . First, $n$ covers $d$ exactly when $\frac{n}{d}$ is prime. If $n = d p$ with $p$ prime and $d ∣ c ∣ n$ , then $c = d k$ and $n = c k'$ for positive integers $k$ and $k'$ with $k k' = p$ , so $k = 1$ or $k' = 1$ , that is, $c = d$ or $c = n$ . If instead $\frac{n}{d} = u v$ with $1 < u, v$ , then $d ≺ d u ≺ n$ , so $n$ does not cover $d$ .

So the covering pairs are those where the larger is $2$ or $3$ times the smaller:

$1 ≺ 2$ , $1 ≺ 3$ , $2 ≺ 4$ , $2 ≺ 6$ , $3 ≺ 6$ , $3 ≺ 9$ , $4 ≺ 12$ , $6 ≺ 12$ , $6 ≺ 18$ , $9 ≺ 18$ , $12 ≺ 36$ , $18 ≺ 36$ .

That is twelve lines. The diagram is a three by three grid standing on a corner, since the divisors are $2^{i} 3^{j}$ with $0 \leq i, j \leq 2$ .

Height. The chain $1 ∣ 2 ∣ 4 ∣ 12 ∣ 36$ has five elements. Suppose a chain had six, listed upwards as $c_{1} ∣ c_{2} ∣ \dots ∣ c_{6}$ . Each quotient $q_{i} = \frac{c_{i + 1}}{c_{i}}$ is an integer at least $2$ , and $q_{1} q_{2} q_{3} q_{4} q_{5} = \frac{c_{6}}{c_{1}}$ , which divides $36$ because $c_{6}$ does. If all five quotients are $2$ , the product is $32$ , which does not divide $36$ ; if one is at least $3$ , the product is at least $3 \times 2^{4} = 48 > 36$ . Either way this is impossible. The height is $5$ .

Width. The set ${4, 6, 9}$ is an antichain: none divides another. The three chains ${1, 2, 4, 12, 36}$ , ${3, 6, 18}$ and ${9}$ cover all nine divisors, so by the lemma on chains and antichains no antichain has more than three elements. The width is $3$ .

3. In the poset ${2, 3, 4, \dots, 12}$ under divisibility, find all minimal and all maximal elements, and decide whether there is a least or a greatest element. Then find, if they exist, $\sup {2, 3}$ , $\sup {4, 6}$ and $\sup {5, 7}$ in this poset.

Solution

An element is minimal when no other element of the set divides it. The numbers $2, 3, 5, 7, 11$ are prime, so their only divisors in the set are themselves, and they are minimal. Every other element has a prime divisor in the set: $4, 6, 8, 10, 12$ are divisible by $2$ and $9$ by $3$ . So the minimal elements are $2, 3, 5, 7, 11$ .

An element is maximal when no proper multiple of it lies in the set, that is, when its double exceeds $12$ . So the maximal elements are $7, 8, 9, 10, 11, 12$ ; the others have $2 \times 2 = 4$ , $6$ , $8$ , $10$ and $12$ in the set.

There are five minimal elements, so there is no least element (a least element would be the only minimal one), and six maximal elements, so no greatest one.

The upper bounds of ${2, 3}$ in the set are its common multiples there, $6$ and $12$ , and $6 ∣ 12$ , so $\sup {2, 3} = 6$ . The only upper bound of ${4, 6}$ is $12$ , so $\sup {4, 6} = 12$ . The set ${5, 7}$ has no upper bound, since $35 > 12$ , so it has no supremum.

4. In $(P ({1, 2, 3, 4}), \subseteq)$ , find all upper bounds and all lower bounds of $S = {{1, 2}, {2, 3}}$ , and $\sup S$ and $\inf S$ . In $(ℕ, ∣)$ , find $\sup {12, 18}$ and $\inf {12, 18}$ .

Solution

A set $U$ is an upper bound of $S$ when ${1, 2} \subseteq U$ and ${2, 3} \subseteq U$ , that is, when ${1, 2, 3} \subseteq U$ . So the upper bounds are ${1, 2, 3}$ and ${1, 2, 3, 4}$ , and the least is $\sup S = {1, 2, 3} = {1, 2} \cup {2, 3}$ .

A set $L$ is a lower bound when $L \subseteq {1, 2}$ and $L \subseteq {2, 3}$ , that is, when $L \subseteq {2}$ . So the lower bounds are $\emptyset$ and ${2}$ , and $\inf S = {2} = {1, 2} \cap {2, 3}$ .

In $(ℕ, ∣)$ , the supremum is the least common multiple and the infimum the greatest common divisor, by the Example and the Now you in the section on lattices. The common multiples of $12$ and $18$ are the multiples of $36$ (the least positive one is $36$ , since $12$ , $24$ are not multiples of $18$ and $36$ is), so $\sup {12, 18} = 36$ , and $\inf {12, 18} = 6$ , computed in the lesson.

Core

5. Let $≺$ be a strict partial order on $A$ (irreflexive and transitive), and define $a ⪯ b$ to mean $a ≺ b$ or $a = b$ . Prove that $⪯$ is a partial order whose strict version is $≺$ again. Prove also that starting from a partial order, passing to its strict version and then back gives the partial order you started with.

Hint

For transitivity of $⪯$ , split on whether either of the two relations is an equality. For antisymmetry, use the asymmetry argument from the lesson.

Solution

Reflexive. For every $a$ , $a = a$ , so $a ⪯ a$ .

Transitive. Let $a ⪯ b$ and $b ⪯ c$ . If $a = b$ , then $a ⪯ c$ is the second relation. If $b = c$ , it is the first. Otherwise $a ≺ b$ and $b ≺ c$ , so $a ≺ c$ by transitivity of $≺$ , and $a ⪯ c$ .

Antisymmetric. Let $a ⪯ b$ and $b ⪯ a$ , and suppose $a \neq b$ . Then $a ≺ b$ and $b ≺ a$ , so $a ≺ a$ by transitivity, contradicting irreflexivity. So $a = b$ .

The strict version of $⪯$ is $≺$ . The strict version relates $a$ to $b$ when $a ⪯ b$ and $a \neq b$ , that is, when ( $a ≺ b$ or $a = b$ ) and $a \neq b$ , which is equivalent to " $a ≺ b$ and $a \neq b$ ". Since $≺$ is irreflexive, $a ≺ b$ already implies $a \neq b$ , so this is just $a ≺ b$ .

The other round trip. Start from a partial order $⪯$ , with strict version $a ≺ b$ meaning $a ⪯ b$ and $a \neq b$ . The relation " $a ≺ b$ or $a = b$ " holds when ( $a ⪯ b$ and $a \neq b$ ) or $a = b$ . If $a ⪯ b$ , then either $a \neq b$ and the first alternative holds, or $a = b$ and the second does. Conversely, each alternative gives $a ⪯ b$ , the second by reflexivity. So the round trip returns $⪯$ .

6. Prove or disprove each claim. (a) If a poset has exactly one maximal element, that element is greatest. (b) If a finite poset has exactly one maximal element, that element is greatest.

Hint

For (a), put an element beside a copy of $ℤ$ with nothing relating the two. For (b), use the theorem on finite posets on the set of elements above a given $x$ .

Solution

(a) False. Let $A = ℤ \cup {m}$ , where $m$ is a new element that is not an integer, ordered by $\leq$ on $ℤ$ and with $m$ related only to itself. This is a partial order: reflexivity, antisymmetry and transitivity hold inside $ℤ$ , and any relation involving $m$ is $m ⪯ m$ . No integer is maximal, since $n ≺ n + 1$ . The element $m$ is maximal, since nothing other than $m$ is related to it. So $m$ is the only maximal element. It is not greatest, since $0 ⪯ m$ fails.

(b) True. Let $A$ be a finite poset whose only maximal element is $m$ , and let $x \in A$ . The set $U = {y \in A : x ⪯ y}$ is finite and contains $x$ , so by the theorem on finite posets, applied to $U$ with the restricted order, it has an element $y$ maximal in $U$ . This $y$ is maximal in $A$ : if $y ≺ z$ for some $z \in A$ , then $x ⪯ y ≺ z$ , so $z \in U$ , contradicting the maximality of $y$ in $U$ . Since $m$ is the only maximal element of $A$ , $y = m$ , and so $x ⪯ m$ . As $x$ was arbitrary, $m$ is greatest.

Part (a) shows where finiteness enters: in $ℤ \cup {m}$ , the set of elements above $0$ has no maximal element, and the argument of (b) breaks at exactly that step.

7. Find the flaw in this argument, show that the claim is false, and prove the claim under the extra hypothesis that every two elements of $P$ have a common upper bound in $P$ .

Claim. Let $P$ be a non-empty poset in which every non-empty chain has an upper bound in $P$ . Then $P$ has a greatest element.

Proof. By Zorn's lemma, $P$ has a maximal element $m$ . Let $x \in P$ . Since $m$ is maximal, it is not the case that $m ≺ x$ . Therefore $x ⪯ m$ . As $x$ was arbitrary, $m$ is greatest.

Hint

Which step would be correct in a total order, and only there? For the counterexample, try the smallest poset with two incomparable elements.

Solution

The flaw is the step from "not $m ≺ x$ " to " $x ⪯ m$ ". In a total order that step is trichotomy, but in a partial order $x$ and $m$ may be incomparable, and then neither $m ≺ x$ nor $x ⪯ m$ holds. The argument confuses maximal with greatest.

The claim is false. Let $P = {a, b}$ with $a$ and $b$ incomparable (so the order is just equality). The non-empty chains are ${a}$ and ${b}$ , with upper bounds $a$ and $b$ . Both $a$ and $b$ are maximal and neither is greatest.

Corrected claim. Suppose also that every two elements of $P$ have a common upper bound. Let $m$ be maximal, as Zorn's lemma provides, and let $x \in P$ . Let $u$ be a common upper bound of $x$ and $m$ . Then $m ⪯ u$ , and $m ≺ u$ is impossible since $m$ is maximal, so $u = m$ . Hence $x ⪯ u = m$ . As $x$ was arbitrary, $m$ is greatest.

8. Prove that among any $n + 1$ numbers chosen from ${1, 2, \dots, 2 n}$ , one divides another. Show that the statement fails for $n$ numbers, and deduce the width of ${1, 2, \dots, 2 n}$ under divisibility.

Hint

Write each number as a power of $2$ times an odd number. How many odd numbers are available?

Solution

Every $k \in ℕ$ can be written as $k = 2^{i} q$ with $i \geq 0$ and $q$ odd: divide $k$ by $2$ as long as the result is even, which stops because the values decrease. The odd part $q$ is determined by $k$ . If $2^{i} q = 2^{j} r$ with $q$ and $r$ odd and, say, $i < j$ , then $q = 2^{j - i} r$ would be even; so $i = j$ and $q = r$ .

For $k \leq 2 n$ the odd part is one of the $n$ odd numbers $1, 3, \dots, 2 n - 1$ . Among $n + 1$ chosen numbers, by the pigeonhole principle two different ones, $2^{i} q$ and $2^{j} q$ , have the same odd part $q$ . They are different, so $i \neq j$ ; say $i < j$ . Then $2^{j} q = 2^{j - i} \cdot 2^{i} q$ , so the first divides the second.

For $n$ numbers the claim fails: take $n + 1, n + 2, \dots, 2 n$ . A proper multiple of any of them is at least twice it, so at least $2 n + 2$ , and is not in the set. So no one of them divides another.

In the language of the lesson, the sets $C_{q} = {2^{i} q : 2^{i} q \leq 2 n}$ for the $n$ odd numbers $q$ are $n$ chains covering ${1, \dots, 2 n}$ , so every antichain has at most $n$ elements, and ${n + 1, \dots, 2 n}$ is an antichain with exactly $n$ . The width is $n$ . For $n = 6$ this is the width $6$ of ${1, \dots, 12}$ found in the lesson, and the chains $C_{q}$ are the six chains used there.

9. Let $L$ be a lattice. Prove that (a) $a ⪯ b$ if and only if $a \lor b = b$ , and dually $a ⪯ b$ if and only if $a \land b = a$ ; (b) $a \land (a \lor b) = a$ and $a \lor (a \land b) = a$ , for all $a, b \in L$ . (c) Deduce that $\gcd (a, lcm (a, b)) = a$ for all $a, b \in ℕ$ .

Hint

For (a), check the two conditions in the definition of supremum. Part (b) then follows from (a) in one line each.

Solution

(a) Suppose $a ⪯ b$ . Then $b$ is an upper bound of ${a, b}$ , since $a ⪯ b$ and $b ⪯ b$ , and every upper bound $v$ of ${a, b}$ has $b ⪯ v$ . So $b$ is the least upper bound: $a \lor b = b$ . Conversely, if $a \lor b = b$ , then $a ⪯ a \lor b = b$ , since the join is an upper bound of ${a, b}$ . The second statement is the first applied to the reverse order, in which joins and meets exchange roles.

(b) Since $a \lor b$ is an upper bound of ${a, b}$ , $a ⪯ a \lor b$ , and the dual half of (a) gives $a \land (a \lor b) = a$ . Since $a \land b$ is a lower bound of ${a, b}$ , $a \land b ⪯ a$ , and the first half of (a), with $a \land b$ in the role of $a$ and $a$ in the role of $b$ , gives $(a \land b) \lor a = a$ . The join of two elements does not depend on their order, since ${a \land b, a}$ and ${a, a \land b}$ are the same set, so $a \lor (a \land b) = a$ .

(c) In $(ℕ, ∣)$ the meet is the greatest common divisor and the join is the least common multiple, as proved in the lesson. So $\gcd (a, lcm (a, b)) = a \land (a \lor b) = a$ by (b). For instance $\gcd (4, lcm (4, 6)) = \gcd (4, 12) = 4$ .

10. Prove or disprove each claim. (a) The lexicographic order on $ℕ \times ℤ$ is a well-order. (b) There is a well-order on $ℤ$ . (c) Every subset of a well-ordered set is well-ordered by the restricted order. (d) If $(W, ⪯)$ is well-ordered, so is $W$ with the reverse order.

Hint

For (b), a bijection between $ℤ$ and $ℕ$ lets you borrow the order of $ℕ$ . For (d), try $ℕ$ .

Solution

(a) False. The subset $S = {(1, z) : z \in ℤ}$ is non-empty and has no least element: for any $(1, z) \in S$ , the element $(1, z - 1)$ is in $S$ and $(1, z - 1) ≺ (1, z)$ by the second clause.

(b) True. Define $g : ℤ \to ℕ$ by $g (z) = 2 z$ for $z \geq 1$ and $g (z) = 1 - 2 z$ for $z \leq 0$ . The values for $z \geq 1$ are even and those for $z \leq 0$ are odd and at least $1$ , so $g$ maps into $ℕ$ , and it is injective: equal values have equal parity, and then $2 z = 2 z'$ or $1 - 2 z = 1 - 2 z'$ gives $z = z'$ . Define $m ⊑ n$ when $g (m) \leq g (n)$ . This is reflexive and transitive because $\leq$ is, antisymmetric because $g (m) = g (n)$ forces $m = n$ , and total because $\leq$ is. Let $S \subseteq ℤ$ be non-empty. Then $g (S)$ is a non-empty subset of $ℕ$ , with a least element $g (s_{0})$ for some $s_{0} \in S$ , and $g (s_{0}) \leq g (s)$ for every $s \in S$ , that is, $s_{0} ⊑ s$ . So $⊑$ is a well-order. It lists $ℤ$ as $0, 1, - 1, 2, - 2, \dots$ .

(c) True. Let $(W, ⪯)$ be well-ordered and $V \subseteq W$ . The restricted order is a total order, since the defining properties are universal statements. A non-empty subset of $V$ is a non-empty subset of $W$ , so it has a least element, and that element is in the subset.

(d) False, unless $W$ is finite. $(ℕ, \leq)$ is well-ordered, but under the reverse order $\geq$ a least element of $ℕ$ would be a greatest natural number, and there is none, since $n < n + 1$ .

11. Let $(A, ⪯)$ be an infinite totally ordered set in which every element has only finitely many predecessors (elements strictly below it). Prove that $A$ is order-isomorphic to $(ℕ, \leq)$ .

Hint

Send each element to one more than its number of predecessors. Show this map is strictly increasing, and that its image contains $n$ whenever it contains $n + 1$ .

Solution

For $a \in A$ , let $pred (a) = {x \in A : x ≺ a}$ , a finite set, and define $f (a) = | pred (a) | + 1$ , a natural number.

$f$ is strictly increasing. Let $a ≺ b$ . Every $x ≺ a$ has $x ≺ b$ by transitivity, so $pred (a) \subseteq pred (b)$ . Also $a \in pred (b)$ and $a \notin pred (a)$ . So $pred (b)$ has at least one more element than $pred (a)$ , and $f (a) < f (b)$ .

$f$ is injective and reflects order. Let $a \neq b$ . By totality, $a ≺ b$ or $b ≺ a$ , so $f (a) < f (b)$ or $f (b) < f (a)$ ; in particular $f (a) \neq f (b)$ . The same reasoning shows that $f (a) \leq f (b)$ implies $a ⪯ b$ : otherwise $b ≺ a$ , and then $f (b) < f (a)$ . So $a ⪯ b$ if and only if $f (a) \leq f (b)$ .

$f$ is surjective. First, the image of $f$ is closed downwards: if $f (b) = n + 1$ with $n \geq 1$ , then $pred (b)$ is a non-empty finite totally ordered set, so it has a greatest element $a$ (by the theorem on finite posets, since a maximal element of a total order is greatest). The predecessors of $a$ are exactly the predecessors of $b$ other than $a$ : if $x ≺ a$ then $x ≺ b$ and $x \neq a$ ; and if $x ≺ b$ with $x \neq a$ , then $x ⪯ a$ because $a$ is greatest in $pred (b)$ , so $x ≺ a$ . So $f (a) = n$ . Second, the image is infinite, since $f$ is injective and $A$ is infinite, so for each $n \in ℕ$ some value $f (b) \geq n$ . Going down from $f (b)$ one step at a time, each value from $f (b)$ down to $1$ is in the image, $n$ among them.

So $f$ is a bijection $A \to ℕ$ with $a ⪯ b$ exactly when $f (a) \leq f (b)$ , an order isomorphism. The hypothesis on predecessors cannot be dropped: in the evens-first order on $ℕ$ , the element $1$ has infinitely many predecessors, and the order is not isomorphic to $(ℕ, \leq)$ .

Challenge

12. Prove that every sequence $x_{1}, x_{2}, \dots, x_{N}$ of $N > r s$ distinct real numbers has an increasing subsequence of more than $r$ terms or a decreasing subsequence of more than $s$ terms. Show that $r s$ terms are not enough.

Hint

First prove that a finite poset with more than $r s$ elements has a chain of more than $r$ elements or an antichain of more than $s$ , using Mirsky's theorem. Then find a partial order on the positions $1, \dots, N$ whose chains are the increasing subsequences.

Solution

Step 1. Let $A$ be a finite poset with more than $r s$ elements, and suppose every chain has at most $r$ elements, so the height $h$ satisfies $h \leq r$ . By Mirsky's theorem, $A$ is the union of $h$ antichains. If each had at most $s$ elements, $A$ would have at most $h s \leq r s$ elements, which is false. So some antichain has more than $s$ elements.

Step 2. On the set of positions ${1, 2, \dots, N}$ , define $i ⊑ j$ when $i \leq j$ and $x_{i} \leq x_{j}$ . This is a partial order: reflexive since $i \leq i$ and $x_{i} \leq x_{i}$ ; antisymmetric since $i \leq j$ and $j \leq i$ give $i = j$ ; transitive since both conditions are transitive.

A chain is a set of positions $i_{1} < i_{2} < \dots < i_{k}$ any two of which are comparable; since $i_{a} < i_{b}$ , comparability means $x_{i_{a}} \leq x_{i_{b}}$ , and as the values are distinct, $x_{i_{1}} < x_{i_{2}} < \dots < x_{i_{k}}$ . So chains are increasing subsequences. An antichain is a set of positions $i_{1} < \dots < i_{k}$ no two of which are comparable; for $i_{a} < i_{b}$ , incomparability means $x_{i_{a}} \leq x_{i_{b}}$ fails, so $x_{i_{a}} > x_{i_{b}}$ . So antichains are decreasing subsequences.

The poset has $N > r s$ elements, so by Step 1 there is an increasing subsequence of more than $r$ terms or a decreasing one of more than $s$ terms.

Sharpness. Take $r$ blocks of $s$ numbers each. Block $t$ , for $t = 1, \dots, r$ , lists $t s, t s - 1, \dots, t s - s + 1$ in decreasing order, so the blocks are decreasing inside and every number in a later block exceeds every number in an earlier one. For $r = 3$ , $s = 2$ this is $2, 1, 4, 3, 6, 5$ . An increasing subsequence takes at most one term from each block, since each block is decreasing, so it has at most $r$ terms. A decreasing subsequence stays inside one block, since a term of a later block is larger than every term of an earlier one, so it has at most $s$ terms. This sequence has $r s$ distinct terms and neither kind of long subsequence.

The result is due to Paul Erdős and George Szekeres, 1935. Problem 14 of the lesson on contrapositive and contradiction proved the case $r = s$ by the pigeonhole principle.

13. Let $X$ be a set and let $F : P (X) \to P (X)$ be monotone: $A \subseteq B$ implies $F (A) \subseteq F (B)$ . Prove that $F$ has a fixed point, a set $S$ with $F (S) = S$ .

Hint

Consider all sets $A$ with $A \subseteq F (A)$ , and take their union. Show it is contained in its own image, then apply $F$ once more.

Solution

Call a set $A \subseteq X$ expanding if $A \subseteq F (A)$ . The empty set is expanding, since $\emptyset \subseteq F (\emptyset)$ . Let $S$ be the union of all expanding sets, a subset of $X$ .

$S \subseteq F (S)$ . Let $x \in S$ . Then $x \in A$ for some expanding set $A$ . Since $A \subseteq S$ and $F$ is monotone, $F (A) \subseteq F (S)$ . So $x \in A \subseteq F (A) \subseteq F (S)$ . As $x$ was arbitrary, $S \subseteq F (S)$ .

$F (S) \subseteq S$ . Applying $F$ to $S \subseteq F (S)$ , monotonicity gives $F (S) \subseteq F (F (S))$ . So $F (S)$ is itself expanding, and therefore it is one of the sets in the union that defines $S$ : $F (S) \subseteq S$ .

By double inclusion, $F (S) = S$ . In the language of the lesson, $S$ is the supremum in $(P (X), \subseteq)$ of the expanding sets, and it is the greatest fixed point: every fixed point is expanding, so is contained in $S$ .

This is the power-set case of the Knaster and Tarski fixed point theorem, and it proves the Schröder and Bernstein theorem of the next lesson. Given injections $f : A \to B$ and $g : B \to A$ , the map $F (C) = A ∖ g (B ∖ f (C))$ on $P (A)$ is monotone; for a fixed point $C$ , the function equal to $f$ on $C$ and to the inverse of $g$ on $A ∖ C$ is a bijection $A \to B$ .

14. A box holds finitely many balls, each labelled with a natural number. A move removes one ball, with label $n$ say, and puts into the box any finite number of new balls (possibly none), each with a label smaller than $n$ . So a ball labelled $1$ can only be removed. Prove that however the moves are chosen, the box is empty after finitely many moves.

Hint

Suppose some play goes on for ever, and choose one whose starting box has the smallest possible largest label. Follow the balls with that largest label.

Solution

A play that never empties the box is an infinite sequence of moves, each legal in the box left by the one before. Suppose, for a contradiction, that infinite plays exist. Each starts from a non-empty box, which has a largest label; by the well-ordering principle, choose an infinite play whose starting box has the least possible largest label $n$ .

No move ever creates a ball with label $n$ or more, since new labels are smaller than the label removed, which is at most $n$ . So the balls labelled $n$ are those present at the start, say $k$ of them, and at most $k$ moves remove one. Hence there is a stage $t$ after which no move removes a ball labelled $n$ .

If $n = 1$ , every move removes a ball and adds none, so the play has at most as many moves as the box has balls, and is finite, a contradiction. So $n \geq 2$ .

From stage $t$ on, every move removes a ball with label at most $n - 1$ and adds balls with smaller labels, and the balls labelled $n$ are never touched. So deleting the balls labelled $n$ from the box at stage $t$ , and from every later box, leaves an infinite sequence of legal moves, starting from a box whose labels are all at most $n - 1$ . That box is not empty, since a move is made from it. This is an infinite play whose starting box has largest label less than $n$ , contradicting the choice of $n$ . So there are no infinite plays.

No bound on the number of moves exists in advance: a single ball labelled $2$ may be replaced by a million balls labelled $1$ , and the play then lasts a million and one moves. That is why no induction on the number of moves or balls works; the argument uses the largest label first and the number of balls carrying it second, which is a lexicographic order in disguise.