Theory of partially-ordered sets (posets) — sets equipped with a binary relation ≤ that is reflexive, antisymmetric and transitive. Central concepts: chains (totally-ordered subsets), antichains (mutually-incomparable subsets), lattices…
order-theory
Dilworth: width(P) = min chain cover
Dilworth 1950 (Ann. Math. 51:161) — the minimum number of totally-ordered chains needed to partition a finite poset P equals the maximum…
Birkhoff: finite distributive lattice ↔ J(P) of down-sets of join-irreducibles
Birkhoff 1937 representation theorem — every finite distributive lattice L is isomorphic to the lattice of down-sets of its subposet of…
Poset / lattice foundations: reflexive-antisymmetric-transitive ≤ and join/meet
A partially-ordered set (P, ≤) is a set P with a binary relation ≤ satisfying reflexivity x ≤ x, antisymmetry x ≤ y ∧ y ≤ x ⇒ x = y, and…
Sperner: width(2^[n]) = C(n, ⌊n/2⌋) exact
Sperner 1928 (Math. Z. 27:544) — the maximum antichain size of the Boolean lattice 2^[n] (power set of {1,...,n} ordered by inclusion) is…
Mirsky: height(2^[n]) = n+1 exact
Mirsky 1971 dual of Dilworth — the maximum chain length in 2^[n] is n+1, achieved by the full flag of successive single-element extensions…
Birkhoff down-set counts: |J(chain_3)|=4, |J(antichain_3)|=8, |J(V)|=5
Exact enumeration of down-sets J(P) for three canonical 3-element posets, demonstrating Birkhoff's representation in action. (1) Chain-3…
Partial order & poset
(P, ≤) where ≤ is reflexive, antisymmetric, transitive. Hasse diagram visualises. Linear extensions count via Stanley-poset polynomial. …
Dedekind cut & completeness
Dedekind 1872: real numbers as cuts of rationals. Order-completeness: every bounded above set has supremum. Defining property of ℝ;…
Zorn's lemma (equivalent to AC)
If every chain in poset P has upper bound, P has maximal element. Equivalent to axiom-of-choice + well-ordering principle. Used to prove…
Galois connection
Pair of monotone maps f: P ↔ Q :g satisfying f(x) ≤ y ⟺ x ≤ g(y). Generalises Galois theory of field extensions. Foundation for closure…
Complete lattice
Lattice in which every subset has supremum + infimum. Knaster-Tarski fixed-point: monotone f: L → L on complete lattice has fixed-point. …
Antichain & Dilworth's theorem
Dilworth 1950: minimum number of chains covering poset = max antichain size. Dual to Mirsky's theorem. Foundational for order-theoretic…
Dilworth's theorem (1950)
Dilworth 1950: in any finite poset, the maximum antichain size equals minimum number of chains in chain-decomposition; LP-duality dual to…
Birkhoff representation (1937)
Birkhoff 1937: every finite distributive lattice is isomorphic to lattice of down-sets of its poset of join-irreducibles; foundational for…
Knaster-Tarski fixed-point theorem
Knaster-Tarski 1928/1955: monotone f: L -> L on complete lattice has set of fixed points forming a complete lattice; basis of…
Galois connection (adjoint pair)
Ore 1944 Galois-connection: monotone pair f: P -> Q, g: Q -> P with f(x) <= y iff x <= g(y); pervasive in formal-concept-analysis +…
Zorn's lemma in posets
Zorn 1935: every poset where every chain has an upper bound contains a maximal element; equivalent to AC + well-ordering; existence-tool…
Scott domain (CPO + algebraic)
Scott 1971-1972 directed-complete-partial-order with bottom; basis of denotational-semantics for lambda-calculus + recursive-function…
Dilworth (1950)
R Dilworth 1950 chain-decomposition; modern modern foundational-text in combinatorial-order + applications to scheduling +…
Zorn lemma (1935)
M Zorn 1935 + Kuratowski 1922 maximal-element; modern equivalent-axiom-of-choice + Hausdorff-maximality + Tukey's lemma.
Knaster-Tarski (1928)
B Knaster 1928 + A Tarski 1955 fixed-point monotone-lattice; modern modern denotational-semantics-fixed-point + program-verification.
Galois connection (Ore 1944)
Ø Ore 1944 Galois-connection; modern formal-concept-analysis Wille 1982 + lattice-based-knowledge-representation + AI ontologies.
Birkhoff representation (1933)
G Birkhoff 1933 representation-theorem distributive-lattice; modern modern domain-theory Scott 1972 + powerdomain semantics.
Dedekind cut (1872)
R Dedekind 1872 cut-construction-of-reals; modern modern foundational-text + reverse-mathematics + descriptive-set-theory.