AFTD Auto-Formalizing Theoretical Domains

pm_minPre_succ

theoremverified

An 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 element k and no earlier prefix-minimal element lies below it.

Statement

open Finset in
theorem pm_minPre_succ {n : ℕ} (P : PMPoset n) (k : ℕ) (hk : k < n) (a : Fin n) :
    a ∈ pmMinPre P (k + 1) ↔
      (a ∈ pmMinPre P k ∧ P.lt ⟨k, hk⟩ a = false) ∨
      (a = ⟨k, hk⟩ ∧ ∀ t ∈ pmMinPre P k, P.lt t ⟨k, hk⟩ = false)
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_exists_min_belowEvery element of a prefix lies above (or is) a minimal element of that prefix.
Used by 1
  • pm_step_eqOne scanning step of the candidate algorithm maintains the invariant that its candidate list is exactly the set of minimal elements of the…

Lean source view module on GitHub

open Finset intheorem pm_minPre_succ {n : ℕ} (P : PMPoset n) (k : ℕ) (hk : k < n) (a : Fin n) :    a ∈ pmMinPre P (k + 1) ↔      (a ∈ pmMinPre P k ∧ P.lt ⟨k, hk⟩ a = false) ∨      (a = ⟨k, hk⟩ ∧ ∀ t ∈ pmMinPre P k, P.lt t ⟨k, hk⟩ = false) := by  simp only [pmMinPre, Finset.mem_filter, Finset.mem_univ, true_and]  constructor  · rintro ⟨ha, hmin⟩    by_cases hak : a.val < k    · left      exact ⟨⟨hak, fun b hb => hmin b (by omega)⟩, hmin _ (by simp)⟩    · right      have hax : a = ⟨k, hk⟩ := Fin.ext (by simp; omega)      refine ⟨hax, fun t ht => ?_⟩      rw [← hax]; exact hmin t (by omega)  · rintro (⟨⟨hak, hmin⟩, hx⟩ | ⟨hax, hmin⟩)    · refine ⟨by omega, fun b hb => ?_⟩      by_cases hbk : b.val < k      · exact hmin b hbk      · have : b = ⟨k, hk⟩ := Fin.ext (by simp; omega)        rw [this]; exact hx    · subst hax      refine ⟨by simp, fun b hb => ?_⟩      by_cases hbk : b.val < k      · by_contra hbx        have hbx' : P.lt b ⟨k, hk⟩ = true := by simpa using hbx        obtain ⟨t, ht, htb⟩ := pm_exists_min_below P k b hbk        have : P.lt t ⟨k, hk⟩ = true := by          rcases htb with e | e          · rw [e]; exact hbx'          · exact P.trans _ _ _ e hbx'        rw [hmin t (by simpa [pmMinPre] using ht)] at this        exact absurd this (by simp)      · have : b = ⟨k, hk⟩ := Fin.ext (by simp; omega)        rw [this]; exact P.irrefl _
See it in the graphDiscuss this resultChallenge it