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.final_all_women_hold← final_all_women_hold (EconCSLib/MarketDesign/Matching/GaleShapley.lean:999): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- final_holding_injective
finalStateholding is injective. - final_all_men_heldAt termination, every man is held by some woman.
- GS.PreferencesList-based preferences:
prefs iis a full permutation ofFin n, ordered from most to least preferred. - GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
- GS.finalState
finalState: rundaRunwith fueln*n + 1frominitState.
- final_holding_injective
- Used by 3
- gs_injective
gs w mis 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…
- gs_injective
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)