holdinv_step
HoldInv is preserved by one DA step. Proof structure: case-analyze on the pair (s.holding p, bestNew p) that drives daStep's decision for woman p. There are four cases, two of which (old hold preserved and new free-man wins) recur in mirrored form depending on whether s.holding p was some h or none. We extract those two arguments into the local helpers preserve_hold and new_hold and dispatch each of the four cases with a single line. Throughout, the key external lemmas are: * pl_free_props — anyone in proposerList p was free and proposed to p. * daStep_nc_free / daStep_nc_held — nextChoice j advances by 1 if j was free, stays put otherwise. * not_isFree_iff — j is not free in s iff some woman holds j.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in lemma holdinv_step (w m : Preferences n) (s : DAState n) (hhold : HoldInv m s) : HoldInv m (daStep w m s)
- Formalizes
- EconCSLib, `holdinv_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.holdinv_step← holdinv_step (EconCSLib/MarketDesign/Matching/GaleShapley.lean:826): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 12
- 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.isFreeMan
iis free insiff no woman holds him. - GS.propTargetThe woman man
iproposes to at cursor indexk(none if out of bounds). - HoldInvHoldInv (Held → Proposed): if woman
pcurrently holds manj, thenjmust already have proposed top— i.e.,pis in the… - 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.not_isFree_iffGS.not_isFree_iff
- GS.daStep_nc_heldGS.daStep_nc_held
- GS.daStep_nc_freeGS.daStep_nc_free
- GS.pref_list_memEvery element of
Fin nappears in a full-permutation list. - GS.daStep_holdingOne step of DA: woman
p's new holding, expanded once. This is the workhorse rewrite for any proof that needs to case-split on what…
- Used by 2
- GS.daRun_NoAchievableRejection
NoAchievableRejectionis preserved bydaRun(threadingHoldInvand holding-injectivity, both also preserved bydaStep). - holdinv_runholdinv_run
- GS.daRun_NoAchievableRejection
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] in/-- `HoldInv` is preserved by one DA step. Proof structure: case-analyze on the pair `(s.holding p, bestNew p)` that drives `daStep`'s decision for woman `p`. There are four cases, two of which (`old hold preserved` and `new free-man wins`) recur in mirrored form depending on whether `s.holding p` was `some h` or `none`. We extract those two arguments into the local helpers `preserve_hold` and `new_hold` and dispatch each of the four cases with a single line. Throughout, the key external lemmas are: * `pl_free_props` — anyone in `proposerList p` was free and proposed to `p`. * `daStep_nc_free` / `daStep_nc_held` — `nextChoice j` advances by 1 if `j` was free, stays put otherwise. * `not_isFree_iff` — `j` is not free in `s` iff some woman holds `j`. -/lemma holdinv_step (w m : Preferences n) (s : DAState n) (hhold : HoldInv m s) : HoldInv m (daStep w m s) := by intro j p hp -- Fold `(daStep w m s).holding p` to the canonical `match` form (see -- `daStep_holding`). This is what lets us name `pl` / `bn` afterwards -- without losing the connection to `hp`. rw [daStep_holding] at hp -- Names matching the inner `let`s of `daStep`. set pl : Fin n → List (Fin n) := fun p' => (Finset.univ.filter (fun k : Fin n => isFree s k && (propTarget m k (s.nextChoice k) == some p'))).val.toList with pl_def set bn : Fin n → Option (Fin n) := fun p' => (pl p').argmin (fun k => (w.prefs p').idxOf k) with bn_def -- `(s.holding p, bn p)` is exactly what `daStep_holding` matches on. change (match s.holding p, bn p with | none, none => none | some h, none => some h | none, some q => some q | some h, some q => if (w.prefs p).idxOf q < (w.prefs p).idxOf h then some q else some h) = some j at hp ---------------------------------------------------------------------------- -- Reusable closer 1: woman `p`'s old hold `h` survives the step (because -- no new proposer outranks him). Then `h = j` and `j`'s cursor doesn't -- advance (since `j` is not free in `s` — woman `p` holds him). ---------------------------------------------------------------------------- have preserve_hold : ∀ {h : Fin n}, h = j → s.holding p = some h → p ∈ (m.prefs j).take ((daStep w m s).nextChoice j) := by rintro h rfl hs -- `rfl` here substitutes `j := h`, so the conclusion is in terms of `h`. have hh_not_free : isFree s h = false := (not_isFree_iff s h).mpr ⟨p, hs⟩ rw [daStep_nc_held hh_not_free] exact hhold h p hs ---------------------------------------------------------------------------- -- Reusable closer 2: a free man `q ∈ proposerList p` becomes (or is) `p`'s -- holder. Then `q = j`, his cursor advances by 1 in `daStep`, and `p` sits -- at index `s.nextChoice q` of `m.prefs q` — so `p` is now within the -- *new* `take` window. ---------------------------------------------------------------------------- have new_hold : ∀ {q : Fin n}, q = j → q ∈ pl p → p ∈ (m.prefs j).take ((daStep w m s).nextChoice j) := by rintro q rfl hq_in -- Substitution: `j := q`. Conclusion is in terms of `q`. have ⟨hfq, hptq⟩ := pl_free_props s m p q hq_in -- `propTarget m q (s.nextChoice q) = some p`, i.e. -- `(m.prefs q)[s.nextChoice q]? = some p`. Unpack via `getElem?_eq_some_iff`. obtain ⟨hq_lt_len, hget⟩ : ∃ h, (m.prefs q)[s.nextChoice q]'h = p := List.getElem?_eq_some_iff.mp hptq -- After the step, `q`'s cursor is `s.nextChoice q + 1`; `p` sits at index -- `s.nextChoice q < s.nextChoice q + 1`, so `p` is inside the new prefix. rw [daStep_nc_free hfq, List.mem_take_iff_idxOf_lt] · -- `(m.prefs q).idxOf p < s.nextChoice q + 1` rw [← hget, (m.valid q).1.idxOf_getElem _ hq_lt_len] omega · exact pref_list_mem _ (m.valid q).1 (m.valid q).2 p ---------------------------------------------------------------------------- -- Main case split — four cases, each one liner. ---------------------------------------------------------------------------- cases hs : s.holding p with | none => cases hb : bn p with | none => -- (none, none): match returns `none`, contradicting `hp : … = some j`. rw [hs, hb] at hp; exact absurd hp (by simp) | some q => -- (none, some q): new proposer `q` takes the slot; `q = j`. rw [hs, hb] at hp exact new_hold (Option.some.inj hp) (List.argmin_mem hb) | some h => cases hb : bn p with | none => -- (some h, none): old hold kept; `h = j`. rw [hs, hb] at hp exact preserve_hold (Option.some.inj hp) hs | some q => -- (some h, some q): outcome depends on whether `q` outranks `h`. rw [hs, hb] at hp -- The match reduces definitionally to an `if`; force the reduction so -- `split_ifs` can see the conditional. dsimp only at hp split_ifs at hp with hlt · -- `q` upgrades: same as Case 2 above. exact new_hold (Option.some.inj hp) (List.argmin_mem hb) · -- `h` stays: same as Case 3 above. exact preserve_hold (Option.some.inj hp) hs