AFTD Auto-Formalizing Theoretical Domains

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

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}
See it in the graphDiscuss this resultChallenge it