holding_injective_step
theoremverifiedformalizationimported Lean
In daStep, holding remains injective.
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 holding_injective_step (s : DAState n) (hinj : ∀ j1 j2 : Fin n, ∀ i : Fin n, s.holding j1 = some i → s.holding j2 = some i → j1 = j2) : ∀ j1 j2 : Fin n, ∀ i : Fin n, (daStep w m s).holding j1 = some i → (daStep w m s).holding j2 = some i → j1 = j2
- Formalizes
- EconCSLib, `holding_injective_step`
- 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.holding_injective_step← holding_injective_step (EconCSLib/MarketDesign/Matching/GaleShapley.lean:382): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- pl_free_propsHelper: membership in the proposerList implies freedom and proposal target.
- 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.daStepOne step of standard men-proposing DA. All free men propose; women pick the best of {held, new proposers} by rank; free men advance their…
- GS.isFreeMan
iis free insiff no woman holds him. - GS.propTargetThe woman man
iproposes to at cursor indexk(none if out of bounds). - GS.isFree_iffGS.isFree_iff
- Used by 6
- holding_injective_runOver
daRun, holding remains injective. - nc_le_n_run
nextChoice i ≤ noverdaRun. - GS.daRun_NoAchievableRejection
NoAchievableRejectionis preserved bydaRun(threadingHoldInvand holding-injectivity, both also preserved bydaStep). - rsinv_runRSInv over daRun.
- nc_sum_le_nn
∑ nextChoice ≤ n * nis preserved overdaRun. - nc_sum_growsAfter
fuelrounds ending with free men,∑ nextChoicegrew by ≥fuel.
- holding_injective_runOver
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/-- In `daStep`, `holding` remains injective. -/lemma holding_injective_step (s : DAState n) (hinj : ∀ j1 j2 : Fin n, ∀ i : Fin n, s.holding j1 = some i → s.holding j2 = some i → j1 = j2) : ∀ j1 j2 : Fin n, ∀ i : Fin n, (daStep w m s).holding j1 = some i → (daStep w m s).holding j2 = some i → j1 = j2 := by intro j1 j2 i hj1 hj2 -- The proposerList and bestNew for each woman let pl : Fin n → List (Fin n) := fun j => (Finset.univ.filter (fun k => isFree s k && (propTarget m k (s.nextChoice k) == some j))).val.toList have pl_disj : ∀ k : Fin n, ∀ j1' j2' : Fin n, k ∈ pl j1' → k ∈ pl j2' → j1' = j2' := by intro k j1' j2' hk1 hk2 exact Option.some.inj ((pl_free_props s m j1' k hk1).2.symm.trans (pl_free_props s m j2' k hk2).2) let bn : Fin n → Option (Fin n) := fun j => (pl j).argmin (fun k => (w.prefs j).idxOf k) have bn_mem : ∀ j p : Fin n, bn j = some p → p ∈ pl j := fun j p hp => List.argmin_mem hp -- `newHolding j = some i` means i came via bn j or from s.holding j have result_source : ∀ j : Fin n, (daStep w m s).holding j = some i → bn j = some i ∨ s.holding j = some i := by intro j hj simp only [daStep] at hj rcases hs : s.holding j with _ | h <;> rcases hb : bn j with _ | p <;> simp only [hs, show (Finset.univ.filter (fun k => isFree s k && (propTarget m k (s.nextChoice k) == some j))).val.toList.argmin (fun k => idxOf k (w.prefs j)) = bn j from rfl] at hj <;> simp_all [bn] <;> split_ifs at hj with hlt <;> simp_all rcases result_source j1 hj1 with hbn1 | hold1 · -- i came via proposals to j1 → i was free in s have hi_free : isFree s i = true := (pl_free_props s m j1 i (bn_mem j1 i hbn1)).1 rcases result_source j2 hj2 with hbn2 | hold2 · -- both via proposals → j1 = j2 (same man can only propose to one woman) exact pl_disj i j1 j2 (bn_mem j1 i hbn1) (bn_mem j2 i hbn2) · -- j2 via old holding: i was free but s.holding j2 = some i → contradiction rw [isFree_iff] at hi_free; exact absurd hold2 (hi_free j2) · rcases result_source j2 hj2 with hbn2 | hold2 · -- j1 via old holding, j2 via proposals → contradiction have hi_free : isFree s i = true := (pl_free_props s m j2 i (bn_mem j2 i hbn2)).1 rw [isFree_iff] at hi_free; exact absurd hold1 (hi_free j1) · -- both via old holding → induction hypothesis exact hinj j1 j2 i hold1 hold2