AFTD Auto-Formalizing Theoretical Domains

apx_search_sound

lemmaverified

If the pruned search succeeds, every seat assignment choosing candidates for the profiles has a population paradox between two of them.

Statement

lemma apx_search_sound (g : (Fin 4 → ℕ) → (Fin 4 → ℕ)) (Pos : (Fin 4 → ℕ) → Prop) :
    ∀ todo done, apx_search done todo = true → (∀ x ∈ done, g x.1 = x.2 ∧ Pos x.1) →
      (∀ pc ∈ todo, g pc.1 ∈ pc.2 ∧ Pos pc.1) →
      ∃ p q, Pos p ∧ Pos q ∧ apx_paradox p (g p) q (g q) = true
Source
step towards quota_population_monotone_incompatible_four_states_common_house (common-house-size variant left open by arXiv:2608.02759, Sec. 5; cf. arXiv:2202.11061, Sec. 3.1)
Verified
06 Oct 2026
Axioms
Quot.soundpropext
Built on 2
  • apx_paradoxBoolean test for a population paradox between two four-state profiles with given seat vectors.
  • apx_searchPruned search over candidate seat vectors for a list of profiles; succeeds iff every complete assignment contains a population paradox.
Used by 1

Lean source view module on GitHub

/-- Soundness of `apx_search`: if it succeeds, every seat assignment `g` that agrees with the done part and picks candidates for the pending profiles has a population paradox between two of the profiles. -/lemma apx_search_sound (g : (Fin 4 → ℕ) → (Fin 4 → ℕ)) (Pos : (Fin 4 → ℕ) → Prop) :    ∀ todo done, apx_search done todo = true → (∀ x ∈ done, g x.1 = x.2 ∧ Pos x.1) →      (∀ pc ∈ todo, g pc.1 ∈ pc.2 ∧ Pos pc.1) →      ∃ p q, Pos p ∧ Pos q ∧ apx_paradox p (g p) q (g q) = true := by  intro todo  induction todo with  | nil => intro done h; simp [apx_search] at h  | cons pc rest ih =>    intro done h hdone htodo    obtain ⟨p, cs⟩ := pc    simp only [apx_search, List.all_eq_true] at h    obtain ⟨hmem, hpos⟩ := htodo (p, cs) (by simp)    have := h (g p) hmem    rcases Bool.or_eq_true_iff.1 this with hc | hs    · obtain ⟨x, hx, hxp⟩ := List.any_eq_true.1 hc      obtain ⟨hgx, hposx⟩ := hdone x hx      rcases Bool.or_eq_true_iff.1 hxp with h1 | h1      · exact ⟨x.1, p, hposx, hpos, by rw [hgx]; exact h1⟩      · exact ⟨p, x.1, hpos, hposx, by rw [hgx]; exact h1⟩    · refine ih ((p, g p) :: done) hs ?_ (fun pc hpc => htodo pc (by simp [hpc]))      intro x hx      rcases List.mem_cons.1 hx with rfl | hx      · exact ⟨rfl, hpos⟩      · exact hdone x hx
See it in the graphDiscuss this resultChallenge it