AFTD Auto-Formalizing Theoretical Domains

pm_recolor

theoremverified

Recolouring that preserves colour-equality on every fact preserves all answers.

Statement

theorem pm_recolor {n : ℕ} (F : List (Fin n × Fin n × PMAns)) (c c' : Fin n → Bool)
    (ρ : Fin n → ℤ) (hc : ∀ f ∈ F, (c' f.1 = c' f.2.1 ↔ c f.1 = c f.2.1)) :
    ∀ f ∈ F, (pmFam c' ρ).ans f.1 f.2.1 = (pmFam c ρ).ans f.1 f.2.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 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…
  • 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…
  • pm_ans_famExplicit form of the oracle on a two-chain poset.
Used by 2
  • pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
  • pm_leafAt a leaf with positive potential, two realisations consistent with all answers have different sets of minimal elements (so no output can…

Lean source view module on GitHub

/-- Recolouring that preserves colour-equality on every fact preserves all answers. -/theorem pm_recolor {n : ℕ} (F : List (Fin n × Fin n × PMAns)) (c c' : Fin n → Bool)    (ρ : Fin n → ℤ) (hc : ∀ f ∈ F, (c' f.1 = c' f.2.1 ↔ c f.1 = c f.2.1)) :    ∀ f ∈ F, (pmFam c' ρ).ans f.1 f.2.1 = (pmFam c ρ).ans f.1 f.2.1 := by  intro f hf  have h := hc f hf  rw [pm_ans_fam, pm_ans_fam]  have h' : (c' f.2.1 = c' f.1 ↔ c f.2.1 = c f.1) := by    constructor <;> intro e <;> exact (by      first      | exact (h.1 e.symm).symm      | exact (h.2 e.symm).symm)  simp only [h, h']
See it in the graphDiscuss this resultChallenge it