AFTD Auto-Formalizing Theoretical Domains

pm_step_facts

theoremverified

The adversary only appends the query and its answer to the list of facts.

Statement

theorem pm_step_facts {n : ℕ} (S : PMState n) (a b : Fin n) :
    (S.step a b).2.facts = (a, b, (S.step a b).1) :: S.facts
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
  • 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.stepThe adversary's move on query (a, b): the answer, and the new state.
Used by 1
  • pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…

Lean source view module on GitHub

/-- The adversary only appends the query and its answer to the list of facts. -/theorem pm_step_facts {n : ℕ} (S : PMState n) (a b : Fin n) :    (S.step a b).2.facts = (a, b, (S.step a b).1) :: S.facts := by  unfold PMState.step  split_ifs <;> rfl
See it in the graphDiscuss this resultChallenge it