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