AFTD Auto-Formalizing Theoretical Domains

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

/-- 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])
See it in the graphDiscuss this resultChallenge it