Early undergraduateFoundationsPlanned
Orders, lattices and well-orders
Partial and total orders, Hasse diagrams, maximal elements and suprema, lattices and well-orders, with Zorn's lemma stated as a tool to be justified later.
math.found.order-theory
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
Builds on
Relations, equivalence relations and partitionsProof: direct, contrapositive, contradiction and induction
Required prerequisites, all the way down: 11
You will learn to
- Verify the partial-order axioms and draw Hasse diagrams for finite posets such as divisibility on {1, …, 12} and inclusion on P({1, 2, 3}).
- Distinguish maximal from greatest elements, and upper bounds from least upper bounds, with examples.
- Define lattices and well-orders, and show that ℕ is well-ordered by ≤ while ℤ and ℚ are not.
Definition
- A partial order on P is a relation ≤ that is reflexive, antisymmetric and transitive.
- A lattice is a poset in which every pair of elements has a least upper bound (join) and a greatest lower bound (meet).
- A well-order is a total order in which every non-empty subset has a least element.
- Zorn's lemma: if every chain in a non-empty poset has an upper bound, then the poset has a maximal element.
Theorem
- Every finite non-empty poset has a maximal element.
- (P(A), ⊆) is a lattice with join ∪ and meet ∩.
- Over ZF, Zorn's lemma is equivalent to the axiom of choice.
Common misconceptions
- Treating 'maximal' and 'greatest' as synonyms.
- Assuming every partial order is total.
- Thinking a least upper bound of a subset must belong to that subset.
Leads to
Optional discoveries
- Categories A preorder is exactly a category with at most one morphism between any two objects; order-preserving maps between preorders are then exactly functors.
- Algebraic structures: monoids, groups and rings A lattice can equivalently be described as a set with two operations ∧ and ∨ satisfying associative, commutative and absorption laws.
Learning pathways
Further reading
- B. A. Davey and H. A. Priestley, Introduction to Lattices and Order (1990)