poset_dimension
def
For a relation r : α → α → Prop on α, poset_dimension r is the infimum in ℕ of the set of natural numbers d such that there exists a family of linear orders R : Fin d → LinearOrder α satisfying is_poset_realizer r R.
Statement
noncomputable def poset_dimension {α : Type*} (r : α → α → Prop) : ℕ
- Defined in
- Dushnik and Miller, Partially ordered sets, Amer. J. Math. 63 (1941), pp. 600-620
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Built on 1
- is_poset_realizerGiven a relation r : α → α → Prop on a type α and an indexed family R : ι → LinearOrder α of linear orders on α, is_poset_realizer r R is…
- Used by 2
- bipartite_subgraph_poset_dimension_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
- bipartite_subgraph_poset_dimension_pow_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
Read back from the Lean
Given a type α and a binary relation r on α, poset_dimension r is defined as the infimum in ℕ (sInf) of the set of all natural numbers d such that there exists a family of d linear orders on α, indexed by Fin d, that realizes r (meaning that for all x, y : α, r x y holds if and only if x ≤ y in every linear order of the family).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The Dushnik-Miller dimension of a relation r on α as the minimum size of a realizer. -/ noncomputable def poset_dimension {α : Type*} (r : α → α → Prop) : ℕ := sInf {d : ℕ | ∃ R : Fin d → LinearOrder α, is_poset_realizer r R}