AFTD Auto-Formalizing Theoretical Domains

pm_exists_min_below

theoremverified

Every element of a prefix lies above (or is) a minimal element of that prefix.

Statement

open Finset in
theorem pm_exists_min_below {n : ℕ} (P : PMPoset n) (k : ℕ) (b : Fin n) (hb : b.val < k) :
    ∃ t ∈ pmMinPre P k, t = b ∨ P.lt t b = true
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 2
  • 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}.
Used by 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…

Lean source view module on GitHub

open Finset in/-- Every element of a prefix lies above (or is) a minimal element of that prefix. -/theorem pm_exists_min_below {n : ℕ} (P : PMPoset n) (k : ℕ) (b : Fin n) (hb : b.val < k) :    ∃ t ∈ pmMinPre P k, t = b ∨ P.lt t b = true := by  set D : Finset (Fin n) := Finset.univ.filter (fun c => c.val < k ∧ (c = b ∨ P.lt c b = true))    with hD  have hbD : b ∈ D := by simp [hD, hb]  obtain ⟨c, hcD, hcmin⟩ := Finset.exists_min_image D    (fun c => (Finset.univ.filter (fun d => P.lt d c = true)).card) ⟨b, hbD⟩  simp only [hD, Finset.mem_filter, Finset.mem_univ, true_and] at hcD  refine ⟨c, ?_, hcD.2⟩  simp only [pmMinPre, Finset.mem_filter, Finset.mem_univ, true_and]  refine ⟨hcD.1, fun d hd => ?_⟩  by_contra hdc  have hdc' : P.lt d c = true := by simpa using hdc  have hdD : d ∈ D := by    simp only [hD, Finset.mem_filter, Finset.mem_univ, true_and]    refine ⟨hd, Or.inr ?_⟩    rcases hcD.2 with e | e    · rw [← e]; exact hdc'    · exact P.trans d c b hdc' e  have hle := hcmin d hdD  have hsub : Finset.univ.filter (fun e => P.lt e d = true) ⊂ Finset.univ.filter (fun e => P.lt e c = true) := by    refine Finset.ssubset_iff_of_subset ?_ |>.2 ⟨d, ?_, ?_⟩    · intro e he      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at he ⊢      exact P.trans e d c he hdc'    · simp [hdc']    · simp [P.irrefl]  have := Finset.card_lt_card hsub  omega
See it in the graphDiscuss this resultChallenge it