pm_step_eq
theoremverified
One scanning step of the candidate algorithm maintains the invariant that its candidate list is exactly the set of minimal elements of the current prefix.
Statement
open Finset in theorem pm_step_eq {n : ℕ} (P : PMPoset n) (k : ℕ) (hk : k < n) (old new : List (Fin n)) (hold : old.toFinset = pmMinPre P k) (h : ∀ a, a ∈ new ↔ (a ∈ old ∧ P.lt ⟨k, hk⟩ a = false) ∨ (a = ⟨k, hk⟩ ∧ ∀ t ∈ old, P.lt t ⟨k, hk⟩ = false)) : new.toFinset = pmMinPre P (k + 1)
- 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).
- pmMinPreMinimal elements of the prefix {0, …, k−1}.
- pm_minPre_succAn element is minimal in the prefix of length k+1 iff it was minimal in the prefix of length k and is not above element k, or it is…
- 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.
open Finset intheorem pm_step_eq {n : ℕ} (P : PMPoset n) (k : ℕ) (hk : k < n) (old new : List (Fin n)) (hold : old.toFinset = pmMinPre P k) (h : ∀ a, a ∈ new ↔ (a ∈ old ∧ P.lt ⟨k, hk⟩ a = false) ∨ (a = ⟨k, hk⟩ ∧ ∀ t ∈ old, P.lt t ⟨k, hk⟩ = false)) : new.toFinset = pmMinPre P (k + 1) := by ext a rw [List.mem_toFinset, h a, pm_minPre_succ P k hk, ← hold] simp only [List.mem_toFinset]