AFTD Auto-Formalizing Theoretical Domains

PMState.Inv

def

The adversary invariant.

Statement

def PMState.Inv {n : ℕ} (S : PMState n) : Prop
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 3
  • 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…
  • PMSatA list of query/answer facts is satisfied by P.
  • 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…
Used by 10
  • pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
  • pm_init_invThe initial adversary state (all elements alive, every element its own component) satisfies the adversary invariant.
  • pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • pm_inv_sameAdversary case a = b: invariant kept, potential unchanged.
  • pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
  • pm_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…
  • pm_inv_diffcolAdversary case: same component, different colours (answer ∥, forced).
  • pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.

Lean source view module on GitHub

/-- The adversary invariant. -/
def PMState.Inv {n : ℕ} (S : PMState n) : Prop :=
  (∀ f ∈ S.facts, S.comp f.1 = S.comp f.2.1) ∧
  PMSat (pmFam S.col S.rk) S.facts ∧
  (∀ f ∈ S.facts, f.1 ∈ S.alive → f.2.1 ∈ S.alive → f.1 ≠ f.2.1 →
      S.col f.1 ≠ S.col f.2.1) ∧
  (∀ x ∈ S.alive, S.rk x = (x.val : ℤ)) ∧
  (∀ x, x ∉ S.alive → (n : ℤ) + S.alive.card ≤ S.rk x) ∧
  Function.Injective S.rk ∧
  (∀ x, ∃ a ∈ S.alive, S.comp a = S.comp x)
See it in the graphDiscuss this resultChallenge it