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
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.
/-- 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