Lattice Theory Foundations
Partial Orders, Posets and Bounds
Partial orders, the posets they generate, and the bound notions — upper and lower bounds, suprema and infima — that make the order-theoretic definition of a lattice possible.
Learning objectives
- State the three conditions defining a partial order
- Distinguish partial orders from total orders and identify chains
- Compute least upper bounds and greatest lower bounds in concrete posets
Partial orders
A binary relation ≤ on a set A is a partial order if it holds identically that (i) a ≤ a (reflexivity); (ii) a ≤ b and b ≤ a imply a = b (antisymmetry); (iii) a ≤ b and b ≤ c imply a ≤ c (transitivity).
If in addition every pair is comparable — for all a, b either a ≤ b or b ≤ a — the order is total.
- poset
- a non-empty set with a partial order on it
- chain
- a totally ordered set; also called linearly ordered
- <em>a</em> < <em>b</em>
- a ≤ b but a ≠ b
- <em>a</em> ≺ <em>b</em>
- b covers a: a < b with nothing strictly between
Three standard examples
| Set | Order | Total? | Where it reappears |
|---|---|---|---|
| Su(A), the power set | ⊆ inclusion | No | Model for Sub(A) and Con(A) |
| Natural numbers | “divides” | No | Distributive lattice under lcm and gcd |
| Real numbers | usual ≤ | Yes | The motivating case; a chain |
Most concepts developed for the real numbers that involve only order — bounds, suprema, monotonicity, completeness — generalise to posets unchanged. What does not generalise is anything using totality.
Bounds, suprema and infima
Let A be a subset of a poset P. An element p of P is an upper bound for A if a ≤ p for every a in A. It is the least upper bound (l.u.b., or supremum, sup A) if additionally p ≤ q for every upper bound q of A.
Greatest lower bound (g.l.b., infimum, inf A) is defined dually. Antisymmetry guarantees that suprema and infima, when they exist, are unique — which is why one may speak of the least upper bound.
In an arbitrary poset a subset need have neither a supremum nor an infimum. In the rationals under the usual order, the set of rationals whose square is below 2 has upper bounds but no least one. Lattices are precisely the posets where every pair has both; complete lattices are where every subset does.
Hasse diagrams
Finite posets are drawn using the covering relation: a is placed below b with a line between them exactly when b covers a. Order is then read off by following upward paths.
Reading a diagram
- Upward path from a to b means a ≤ b.
- No path either way means the elements are incomparable.
- The join a ∨ b is the lowest element reachable upward from both.
- The meet a ∧ b is the highest element reachable downward from both.
The two five-element lattices that dominate Chapter I — M5 and N5 — are best held in mind as diagrams, and are treated in detail in the forbidden-sublattice page.
Frequently asked questions
Why require antisymmetry?
Without it, suprema would not be unique and the correspondence between orders and lattice operations would break down. A reflexive transitive relation without antisymmetry is a preorder, and quotienting by mutual comparability turns it into a partial order.
Is every finite poset a lattice?
No. A four-element poset with two incomparable minimal elements below two incomparable maximal elements has pairs with two incomparable upper bounds and hence no least one.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section I.1, book pages 6-8.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.