AFTD Auto-Formalizing Theoretical Domains

final_all_women_hold

theoremverifiedformalizationimported Lean

At termination, every woman holds some man.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
variable (w m : Preferences n) in
lemma final_all_women_hold :
    ∀ j : Fin n, ∃ i : Fin n, (finalState w m).holding j = some i
Formalizes
EconCSLib, `final_all_women_hold`
Lean proof
By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at 1a88f809b538 (Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 3
  • gs_injectivegs w m is injective.
  • galeShapley_isStableGale-Shapley stability: the DA output has no blocking pair. The statement is in the *market* frame (IsBlocking … (i : M) (j : W)).…
  • GS.galeShapley_isProposingOptimalMen-optimal stable matching (Gale–Shapley 1962, [MSZ 22.10]): in the men-proposing DA, every man's GS partner is at least as preferred…

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen List Finset inopen GS invariable {n : ℕ} [NeZero n] invariable (w m : Preferences n) in/-- At termination, every woman holds some man. -/lemma final_all_women_hold :    ∀ j : Fin n, ∃ i : Fin n, (finalState w m).holding j = some i := by  intro j  by_contra hnone  push_neg at hnone  -- j holds nobody, but every man is held by some woman ≠ j (pigeon-hole).  have hall := final_all_men_held w m  have hinj := final_holding_injective w m  have hf : ∀ i : Fin n, ∃ j' : Fin n, j' ≠ j ∧ (finalState w m).holding j' = some i := by    intro i    obtain ⟨j', hj'⟩ := hall i    exact ⟨j', fun heq => absurd (heq ▸ hj') (hnone i), hj'⟩  -- Inject Fin n → (univ \ {j}) of size n-1 → contradiction.  let f : Fin n → (Finset.univ.erase j : Finset (Fin n)) := fun i =>    ⟨(hf i).choose, Finset.mem_erase.mpr ⟨(hf i).choose_spec.1, Finset.mem_univ _⟩⟩  have hfinj : Function.Injective f := by    intro i1 i2 heq    have h1 : (finalState w m).holding ((hf i1).choose) = some i1 := (hf i1).choose_spec.2    have h2 : (finalState w m).holding ((hf i2).choose) = some i2 := (hf i2).choose_spec.2    have hv : (hf i1).choose = (hf i2).choose := congrArg Subtype.val heq    rw [hv] at h1    exact Option.some.inj (h1.symm.trans h2)  have hcard : (Finset.univ.erase j : Finset (Fin n)).card = n - 1 := by    rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin]  have : Fintype.card (Fin n) ≤ Fintype.card ↥(Finset.univ.erase j : Finset (Fin n)) :=    Fintype.card_le_of_injective _ hfinj  rw [Fintype.card_coe, hcard, Fintype.card_fin] at this  exact absurd this (by have hpos := NeZero.pos n; omega)
See it in the graphDiscuss this resultChallenge it