pm_inv_same
theoremverified
Adversary case a = b: invariant kept, potential unchanged.
Statement
theorem pm_inv_same {n : ℕ} (S : PMState n) (hI : S.Inv) (a : Fin n) : ({ S with facts := (a, a, PMAns.inc) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with facts := (a, a, PMAns.inc) :: S.facts } : PMState n).pot + 1
- 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 5
- PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
- pm_ans_famExplicit form of the oracle on a two-chain poset.
- PMStateThe state of the adversary: a colouring (which of the two chains), ranks, a component label, the set of "alive" elements (not yet shown to…
- PMState.InvThe adversary invariant.
- PMState.potThe potential: (number of components − 1) + (number of alive elements − 2).
- Used by 1
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
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.
/-- Adversary case `a = b`: invariant kept, potential unchanged. -/theorem pm_inv_same {n : ℕ} (S : PMState n) (hI : S.Inv) (a : Fin n) : ({ S with facts := (a, a, PMAns.inc) :: S.facts } : PMState n).Inv ∧ S.pot ≤ ({ S with facts := (a, a, PMAns.inc) :: S.facts } : PMState n).pot + 1 := by obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hI refine ⟨⟨?_, ?_, ?_, h4, h5, h6, h7⟩, ?_⟩ · intro f hf rcases List.mem_cons.1 hf with rfl | hf · rfl · exact h1 f hf · intro f hf rcases List.mem_cons.1 hf with rfl | hf · simp [pm_ans_fam] · exact h2 f hf · intro f hf rcases List.mem_cons.1 hf with rfl | hf · intro _ _ h; exact absurd rfl h · exact h3 f hf · simp [PMState.pot]