pm_alg_correct
theoremverifiedformalization
The algorithm is correct on every width-2 poset.
Statement
theorem pm_alg_correct (n : ℕ) : (pmAlg (n := n) n 0 []).Correct2- Formalizes
- Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4, Theorem 11 (correctness of the candidate-set algorithm); special case width 2
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
- pmMinPreMinimal elements of the prefix {0, …, k−1}.
- pm_minPre_nThe minimal elements of the full prefix of length n are the minimal elements of the poset.
- pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
- Used by 1
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
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.
/-- The algorithm is correct on every width-2 poset. -/theorem pm_alg_correct (n : ℕ) : (pmAlg (n := n) n 0 []).Correct2 := by intro P hP rw [← pm_minPre_n] exact pm_alg_run P hP n 0 [] (by omega) (by simp) (by simp) (by ext a; simp [pmMinPre])