AFTD Auto-Formalizing Theoretical Domains

is_poset_realizer

def

Given a relation r : α → α → Prop on a type α and an indexed family R : ι → LinearOrder α of linear orders on α, is_poset_realizer r R is the proposition that for all x, y : α, r x y holds if and only if (R i).le x y holds for every i : ι.

Statement

def is_poset_realizer {α : Type*} (r : α → α → Prop) {ι : Type*} (R : ι → LinearOrder α) : Prop
Defined in
Dushnik and Miller, Partially ordered sets, Amer. J. Math. 63 (1941), pp. 600-620
Verified
22 Oct 2026
Axioms
none listed
Used by 2
  • 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…
  • poset_dimensionFor a relation r : α → α → Prop on α, poset_dimension r is the infimum in ℕ of the set of natural numbers d such that there exists a…

Read back from the Lean

The definition is_poset_realizer states that for a binary relation r on a type α and a family of linear orders R on α indexed by a type ι, R is a realizer for r if and only if for all x, y : α, r x y holds if and only if for every index i : ι, x ≤ y in the linear order R i.

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

/-- A family of linear orders R realizes a relation r if r is their intersection. -/
def is_poset_realizer {α : Type*} (r : α → α → Prop) {ι : Type*} (R : ι → LinearOrder α) : Prop :=
  ∀ x y : α, r x y ↔ ∀ i, (R i).le x y
See it in the graphDiscuss this resultChallenge it