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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩