AFTD Auto-Formalizing Theoretical Domains

pm_init_inv

theoremverified

The initial adversary state (all elements alive, every element its own component) satisfies the adversary invariant.

Statement

open Finset in
theorem pm_init_inv (n : ℕ) : (pmInit n).Inv
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
  • PMState.InvThe adversary invariant.
  • pmInitThe adversary's initial state: every element is its own component and alive.
Used by 1
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…

Lean source view module on GitHub

open Finset intheorem pm_init_inv (n : ℕ) : (pmInit n).Inv := by  refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  · intro f hf; simp [pmInit] at hf  · intro f hf; simp [pmInit] at hf  · intro f hf; simp [pmInit] at hf  · intro x _; rfl  · intro x hx; simp [pmInit] at hx  · intro x y h; exact Fin.ext (by simpa [pmInit] using h)  · intro x; exact ⟨x, Finset.mem_univ _, rfl⟩
See it in the graphDiscuss this resultChallenge it