pm_mem_minPre
theoremverified
Every minimal element of the prefix of length k has index below k and no element of index below k lies below it.
Statement
theorem pm_mem_minPre {n : ℕ} (P : PMPoset n) (k : ℕ) (t : Fin n) (ht : t ∈ pmMinPre P k) :
t.val < k ∧ ∀ b : Fin n, b.val < k → P.lt b t = false- Source
- step towards pm_exact_complexity / pm_lower_bound (exact complexity 2n - 3 at width 2, refuting the tightness conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Used by 1
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem pm_mem_minPre {n : ℕ} (P : PMPoset n) (k : ℕ) (t : Fin n) (ht : t ∈ pmMinPre P k) : t.val < k ∧ ∀ b : Fin n, b.val < k → P.lt b t = false := by simpa [pmMinPre] using ht