AFTD Auto-Formalizing Theoretical Domains

is_linear_extension

def

Given a natural number n, a partial order P on Fin n, and a linear order L on Fin n, L is a linear extension of P if for all x y in Fin n, x <= y under P implies x <= y under L.

Statement

def is_linear_extension {n : ℕ} (P : PartialOrder (Fin n)) (L : LinearOrder (Fin n)) : Prop
Defined in
arXiv:2610.18740 Section 5
Verified
21 Oct 2026
Axioms
none listed
Used by 3
  • comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
  • is_compatible_solutionA triple (L, e, U) is a compatible solution for a partial order P on Fin n and rank i if L, {e}, and U partition Fin n with |L| = i - 1,…
  • comparison_tree_correct_for_selection_existsFor every natural number n, strict partial order P on Fin n, and rank 1 ≤ i ≤ n, there exists a comparison decision tree on n elements…

Read back from the Lean

Given a natural number $n$, a partial order $P$ on $\mathrm{Fin}(n)$, and a linear order $L$ on $\mathrm{Fin}(n)$, is_linear_extension P L is defined as the proposition that for all $x, y \in \mathrm{Fin}(n)$, if $x \le y$ in the partial order $P$, then $x \le y$ in the linear order $L$.

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 linear order L on Fin n extends a partial order P if every relation in P holds in L. -/
def is_linear_extension {n : ℕ} (P : PartialOrder (Fin n)) (L : LinearOrder (Fin n)) : Prop := ∀ x y : Fin n, @LE.le (Fin n) P.toLE x y → @LE.le (Fin n) L.toLE x y
See it in the graphDiscuss this resultChallenge it