pm_minPre_n
theoremverified
The minimal elements of the full prefix of length n are the minimal elements of the poset.
Statement
theorem pm_minPre_n {n : ℕ} (P : PMPoset n) : pmMinPre P n = P.minSet- 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 3
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.minSetThe set of minimal elements of P (the output of the 1-selection problem).
- pmMinPreMinimal elements of the prefix {0, …, k−1}.
- Used by 1
- pm_alg_correctThe algorithm is correct on every width-2 poset.
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_minPre_n {n : ℕ} (P : PMPoset n) : pmMinPre P n = P.minSet := by ext a simp [pmMinPre, PMPoset.minSet]