AFTD Auto-Formalizing Theoretical Domains

pmMinPre

def

Minimal elements of the prefix {0, …, k−1}.

Statement

open Finset in
def pmMinPre {n : ℕ} (P : PMPoset n) (k : ℕ) : Finset (Fin n)
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
none listed
Built on 1
  • PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
Used by 7
  • 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…
  • pm_exists_min_belowEvery element of a prefix lies above (or is) a minimal element of that prefix.
  • pm_alg_correctThe algorithm is correct on every width-2 poset.
  • pm_mem_minPreEvery minimal element of the prefix of length k has index below k and no element of index below k lies below it.
  • pm_minPre_nThe minimal elements of the full prefix of length n are the minimal elements of the poset.
  • 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…
  • pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.

Lean source view module on GitHub

open Finset in
/-- Minimal elements of the prefix `{0, …, k−1}`. -/
def pmMinPre {n : ℕ} (P : PMPoset n) (k : ℕ) : Finset (Fin n) :=
  Finset.univ.filter (fun a => a.val < k ∧ ∀ b : Fin n, b.val < k → P.lt b a = false)
See it in the graphDiscuss this resultChallenge it