AFTD Auto-Formalizing Theoretical Domains

pm_fam_width2

theoremverified

Two-chain posets with injective rank have width at most 2.

Statement

theorem pm_fam_width2 {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ)
    (hρ : Function.Injective ρ) : (pmFam c ρ).Width2
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
  • PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
  • 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 2
  • 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_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

/-- Two-chain posets with injective rank have width at most `2`. -/theorem pm_fam_width2 {n : ℕ} (c : Fin n → Bool) (ρ : Fin n → ℤ)    (hρ : Function.Injective ρ) : (pmFam c ρ).Width2 := by  intro a b d hab hbd had  simp only [pmFam, decide_eq_true_eq]  have hne : ∀ x y : Fin n, x ≠ y → ρ x < ρ y ∨ ρ y < ρ x := fun x y h =>    lt_or_gt_of_ne (fun e => h (hρ e))  by_cases h1 : c a = c b  · rcases hne a b hab with h | h    · exact Or.inl ⟨h1, h⟩    · exact Or.inr (Or.inl ⟨h1.symm, h⟩)  · by_cases h2 : c b = c d    · rcases hne b d hbd with h | h      · exact Or.inr (Or.inr (Or.inl ⟨h2, h⟩))      · exact Or.inr (Or.inr (Or.inr (Or.inl ⟨h2.symm, h⟩)))    · have h3 : c a = c d := by        cases ha : c a <;> cases hb : c b <;> cases hd : c d <;> simp_all      rcases hne a d had with h | h      · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inl ⟨h3, h⟩))))      · exact Or.inr (Or.inr (Or.inr (Or.inr (Or.inr ⟨h3.symm, h⟩))))
See it in the graphDiscuss this resultChallenge it