Definition and Basic Properties
Partial Order
Partial order: binary relation ≤ on set P. Conditions: reflexive, antisymmetric, transitive. Formally, for all a,b,c ∈ P:
- Reflexivity: a ≤ a
- Antisymmetry: if a ≤ b and b ≤ a then a = b
- Transitivity: if a ≤ b and b ≤ c then a ≤ c
Notation: (P, ≤) is a partially ordered set (poset).
Comparison with Total Order
Total order: partial order plus comparability (for all a,b ∈ P, either a ≤ b or b ≤ a). Partial orders lack total comparability.
Terminology
Elements a,b are comparable if a ≤ b or b ≤ a; otherwise incomparable. Partial orders model hierarchical, non-linear structures.
Examples of Partial Orders
Set Inclusion
Example: (𝒫(S), ⊆), power set of S ordered by subset relation. Reflexive: A ⊆ A. Antisymmetric: if A ⊆ B and B ⊆ A then A = B. Transitive: A ⊆ B and B ⊆ C implies A ⊆ C.
Divisibility on Integers
Relation | on positive integers. a | b iff a divides b. Reflexive: a | a. Antisymmetric: if a | b and b | a then a = b. Transitive: a | b and b | c implies a | c.
Product Order
On Cartesian products P × Q, partial order defined by (a,b) ≤ (c,d) if a ≤ c in P and b ≤ d in Q.
Posets and Their Structure
Definition of a Poset
Poset: set P with partial order ≤. Elements structured by order relation, allowing incomparable elements.
Minimal and Maximal Elements
Minimal element: no x < m in P. Maximal element: no x > m in P. Not necessarily unique.
Least and Greatest Elements
Least element: l ∈ P with l ≤ x for all x in P. Greatest element: g ∈ P with x ≤ g for all x in P. Unique if exist.
Relation Properties in Partial Orders
Reflexivity
For all a ∈ P, a ≤ a. Ensures relation includes all diagonal pairs.
Antisymmetry
For all a,b ∈ P, if a ≤ b and b ≤ a then a = b. Prevents cycles of equivalences.
Transitivity
For all a,b,c ∈ P, if a ≤ b and b ≤ c then a ≤ c. Ensures order consistency.
Non-Comparability
Partial orders allow pairs (a,b) where neither a ≤ b nor b ≤ a, distinguishing them from total orders.
| Property | Definition |
|---|---|
| Reflexive | ∀a ∈ P, a ≤ a |
| Antisymmetric | ∀a,b ∈ P, (a ≤ b ∧ b ≤ a) ⇒ a = b |
| Transitive | ∀a,b,c ∈ P, (a ≤ b ∧ b ≤ c) ⇒ a ≤ c |
Chains and Antichains
Chains
Chain: subset C ⊆ P where every pair of elements is comparable. Total order within subset.
Antichains
Antichain: subset A ⊆ P where no two distinct elements are comparable. Completely incomparable subset.
Width and Height
Width: size of largest antichain. Height: size of largest chain. Related to Dilworth's and Mirsky's theorems.
| Term | Description |
|---|---|
| Chain | Subset totally ordered |
| Antichain | Subset of incomparable elements |
Hasse Diagrams
Definition
Hasse diagram: graphical representation of poset. Vertices represent elements; edges indicate covering relations.
Covering Relation
a covers b if a > b and no c with a > c > b. Edges drawn upward from lower to higher element.
Construction Rules
Omit loops and transitive edges. Place elements vertically respecting order. Simplifies visual complexity.
Example Hasse diagram for P = {1,2,3,6} with divisibility order:1| \2 3 \ / 6 Linear Extensions and Total Orders
Linear Extension
Linear extension: total order L on P extending partial order ≤. For all a,b ∈ P, if a ≤ b then a ≤_L b.
Existence
Every finite poset admits at least one linear extension (Szpilrajn Extension Theorem).
Applications
Used in scheduling, sorting, topological ordering of DAGs.
Algorithm (Topological Sort) for linear extension of DAG representing poset:1. Identify minimal elements (no incoming edges).2. Select one minimal element, add to linear order.3. Remove selected element and edges from graph.4. Repeat until graph empty. Lattices and Special Posets
Definition of Lattice
Lattice: poset where any two elements a,b have join (least upper bound) and meet (greatest lower bound).
Join and Meet
Join (a ∨ b): smallest x with a ≤ x and b ≤ x. Meet (a ∧ b): greatest y with y ≤ a and y ≤ b.
Examples
Boolean algebra (power set with ⊆), integer divisibility with gcd and lcm.
Applications of Partial Orders
Computer Science
Task scheduling, dependency resolution, type hierarchies, data versioning.
Mathematics
Order theory, combinatorics, lattice theory, topology (specialization order).
Logic and Semantics
Modeling entailment, information ordering, domain theory in denotational semantics.
Algorithms on Partial Orders
Topological Sorting
Order elements linearly consistent with partial order. Used in DAGs.
Finding Minimal/Maximal Elements
Scan elements for no smaller/larger elements in relation.
Computing Width and Height
Width via Dilworth's theorem: maximum antichain equals minimum chain partition size. Height via longest chain search.
Advanced Concepts and Theorems
Szpilrajn Extension Theorem
Every partial order extends to a total order. Fundamental for linearization.
Dilworth's Theorem
Width of poset = minimum number of chains needed to cover P.
Mirsky's Theorem
Height of poset = minimum number of antichains needed to cover P.
Order Dimension
Minimum number of linear orders whose intersection is the partial order.
References
- C. Berge, Graphs and Hypergraphs, North-Holland, 1973, pp. 45-78.
- D. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, 1997, pp. 202-215.
- R. P. Dilworth, "A Decomposition Theorem for Partially Ordered Sets," Annals of Mathematics, vol. 51, 1950, pp. 161-166.
- J. B. Nation, "Notes on Lattice Theory," University of Hawaii, 2010, pp. 1-70.
- E. Szpilrajn, "Sur l'extension de l'ordre partiel," Fundamenta Mathematicae, vol. 16, 1930, pp. 386-389.