AFTD Auto-Formalizing Theoretical Domains

pm_ans_fam

theoremverified

Explicit form of the oracle on a two-chain poset.

Statement

theorem pm_ans_fam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) (a b : Fin n) :
    (pmFam c ρ).ans a b =
      if c a = c b ∧ ρ a < ρ b then PMAns.lt
      else if c b = c a ∧ ρ b < ρ a then PMAns.gt else PMAns.inc
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 4
  • 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…
  • PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
  • 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…
Used by 6
  • 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_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_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
  • 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

/-- Explicit form of the oracle on a two-chain poset. -/theorem pm_ans_fam {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ) (a b : Fin n) :    (pmFam c ρ).ans a b =      if c a = c b ∧ ρ a < ρ b then PMAns.lt      else if c b = c a ∧ ρ b < ρ a then PMAns.gt else PMAns.inc := by  simp [PMPoset.ans, pmFam]
See it in the graphDiscuss this resultChallenge it