The Lumenary · Early undergraduate

Orders, lattices and well-orders

Name: ______________________

Date: ______________________

You will learn to

Verify the axioms of a partial order and draw Hasse diagrams for finite posets such as divisibility on $\{1, \dots, 12\}$ and inclusion on $\mathcal{P}(\{1, 2, 3\})$
Distinguish maximal from greatest elements and upper bounds from least upper bounds, and prove that every finite non-empty poset has a maximal element
Define lattices and complete lattices, identify joins and meets in $(\mathcal{P}(A), \subseteq)$ and $(\N, \mid)$ , and prove the Knaster–Tarski fixed-point theorem
Define well-orders and prove that $\N$ is well-ordered by $\le$ while $\Z$ and $\Q$ are not
State Zorn's lemma and explain why it is needed for infinite posets

1.
Which of these relations are partial orders (reflexive, antisymmetric, transitive)? (Choose all that apply.)
- A. $\le$ on $\R$
- B. $a \mid b$ on $\N$
- C. $a \mid b$ on $\Z$
- D. $\subseteq$ on $\mathcal{P}(A)$
- E. $<$ on $\N$
- F. $a \preceq b \iff |a| \le |b|$ on $\Z$
2.
Consider $\{2, 3, \dots, 10\}$ ordered by divisibility. List all its maximal elements, separated by commas.
3.
In the lattice $(\N, \mid)$ , what is the join (least upper bound) $12 \vee 18$ ?
4.
How many edges (covering pairs) does the Hasse diagram of $(\mathcal{P}(\{1, 2, 3, 4\}), \subseteq)$ have?
5.
Theorem 2 says every finite non-empty poset has a maximal element. Which example shows that the word "finite" cannot simply be dropped?
- A. $(\N, \le)$
- B. $(\N, \mid)$
- C. $(\mathcal{P}(\N), \subseteq)$
- D.the empty poset
6.
Which of these totally ordered sets are well-ordered (every non-empty subset has a least element)? (Choose all that apply.)
- A. $\{1 - \tfrac1n : n = 1, 2, 3, \dots\}$ with the usual $\le$
- B. $\{\tfrac1n : n = 1, 2, 3, \dots\}$ with the usual $\le$
- C. $\{0, -1, -2, \dots\}$ with the reversed order $\ge$
- D. $\{q \in \Q : q \geq 0\}$ with the usual $\le$
7.
Which Lean statement says correctly that every finite non-empty poset has a maximal element?
- A.theorem t {α : Type*} [PartialOrder α] [Fintype α] [Nonempty α] : ∃ m : α, ∀ x, m ≤ x → x = m
- B.theorem t {α : Type*} [PartialOrder α] [Fintype α] [Nonempty α] : ∃ m : α, ∀ x, x ≤ m
- C.theorem t {α : Type*} [PartialOrder α] [Nonempty α] : ∃ m : α, ∀ x, m ≤ x → x = m
- D.theorem t {α : Type*} [PartialOrder α] [Fintype α] : ∃ m : α, ∀ x, m ≤ x → x = m
8.
Knaster–Tarski: a monotone map on a complete lattice has a fixed point. Which examples show that one of the two hypotheses cannot be dropped? (Choose all that apply.)
- A. $x \mapsto x + 1$ on $(\Z, \le)$
- B. $0 \mapsto 1$ , $1 \mapsto 0$ on $(\{0, 1\}, \le)$
- C. $x \mapsto x/2$ on $([0, 1], \le)$
- D. $S \mapsto S$ (the identity) on $\mathcal{P}(A)$
9.
Write linear_extension(elements, leq) that lists the elements of a finite poset in an order compatible with leq (a function returning True when $a \le b$ ): whenever $a \le b$ and $a \neq b$ , $a$ must come before $b$ . Use the idea of Corollary 3, or repeatedly take a minimal element.
Computational — Practice

Answer key — Orders, lattices and well-orders

1.
$\le$ on $\R$ , divisibility on $\N$ and inclusion are partial orders. Divisibility on $\Z$ and comparison of absolute values are preorders (antisymmetry fails for $\pm a$ ), and $<$ is not reflexive.
2.
A number $m$ is maximal when $2m > 10$ , i.e. $m \geq 6$ : so $6, 7, 8, 9, 10$ . Every $m \le 5$ is below $2m \le 10$ . There is no greatest element (nothing in the set is divisible by both $7$ and $9$ ), so this is another poset with many maximal elements and no greatest one.
3.
The upper bounds are the common multiples of $12$ and $18$ , and every common multiple is a multiple of $\operatorname{lcm}(12, 18) = 36$ . So $12 \vee 18 = 36$ , while $12 \wedge 18 = \gcd(12, 18) = 6$ .
4.
A subset $S$ with $k$ elements is covered by the $4 - k$ sets $S \cup \{x\}$ . Summing, $\sum_k \binom 4k (4 - k) = 4 + 12 + 12 + 4 + 0 = 32$ . Equivalently, the Hasse diagram is the $4$ -dimensional cube, which has $4 \cdot 2^3 = 32$ edges.
5.
$(\N, \le)$ has no maximal element, since $n < n + 1$ . Infinite posets may have maximal elements — $(\N, \mid)$ has $0$ and $\mathcal{P}(\N)$ has $\N$ — but they need not; Zorn's lemma gives a sufficient condition (every chain bounded above), which $(\N, \le)$ fails: $\N$ itself is an unbounded chain.
6.
(a) and (c) are well-ordered — both are copies of $(\N, \le)$ . In (b) the whole set has no least element; in (d) the whole set has one, but the positive rationals do not. A total order is a well-order exactly when it has no infinite strictly decreasing sequence (this equivalence uses a weak form of the axiom of choice).
7.
Option (a). Option (b) states the existence of a greatest element, which is false for antichains; (c) drops finiteness and (d) drops non-emptiness, and both become false.
8.
The shift on $\Z$ is monotone on an incomplete lattice and has no fixed point; the swap on $\{0, 1\}$ is a non-monotone map on a complete lattice and has no fixed point. So neither hypothesis can be dropped. The other two examples satisfy both hypotheses and have fixed points, as the theorem predicts.

def linear_extension(elements, leq):
    remaining = list(elements)
    order = []
    while remaining:
        m = next(x for x in remaining
                 if not any(y != x and leq(y, x) for y in remaining))
        order.append(m)
        remaining.remove(m)
    return order

A minimal element always exists among the remaining elements (Theorem 2, applied to the reversed order), so next never fails. Each element is appended only after everything below it, which is exactly the required compatibility — the algorithm known as topological sorting.