AFTD Auto-Formalizing Theoretical Domains

pm_inv_dead

theoremverified

Adversary case: same component and colour, not both alive (answer read off the current two-chain realisation).

Statement

theorem pm_inv_dead {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n)
    (hcomp : S.comp a = S.comp b) (hal : ¬ (a ∈ S.alive ∧ b ∈ S.alive)) :
    ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).Inv ∧
    S.pot ≤
      ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: 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
  • PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
  • pmFamThe poset that is a disjoint union of (at most) two chains: elements of the same colour c are ordered by the rank ρ, elements of different…
  • 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

/-- Adversary case: same component and colour, not both alive (answer read off the current two-chain realisation). -/theorem pm_inv_dead {n : ℕ} (S : PMState n) (hI : S.Inv) (a b : Fin n)    (hcomp : S.comp a = S.comp b) (hal : ¬ (a ∈ S.alive ∧ b ∈ S.alive)) :    ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: S.facts } : PMState n).Inv ∧    S.pot ≤      ({ S with facts := (a, b, (pmFam S.col S.rk).ans a b) :: 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    · exact hcomp    · exact h1 f hf  · intro f hf    rcases List.mem_cons.1 hf with rfl | hf    · rfl    · exact h2 f hf  · intro f hf    rcases List.mem_cons.1 hf with rfl | hf    · intro ha hb _; exact absurd ⟨ha, hb⟩ hal    · exact h3 f hf  · simp [PMState.pot]
See it in the graphDiscuss this resultChallenge it