AFTD Auto-Formalizing Theoretical Domains

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

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