HoldInv
defimported Lean
HoldInv (Held → Proposed): if woman p currently holds man j, then j must already have proposed to p — i.e., p is in the proposed-prefix (m.prefs j).take (s.nextChoice j) of j's preference list. This is the converse direction of [JInv]: JInv says proposed ⇒ held; HoldInv says held ⇒ proposed. Together they make the two-sided correspondence between cursors and holdings airtight. HoldInv is the one the stability proof's "the holder must be at least as preferred as the blocker" step relies on, via RSInv — see the proof sketch of [galeShapley_isStable] and the preservation lemma [holdinv_step].
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in def HoldInv (m : Preferences n) (s : DAState n) : Prop
- Defined in
- EconCSLib, `HoldInv`
- 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← HoldInv (EconCSLib/MarketDesign/Matching/GaleShapley.lean:805): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 2
- GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
- GS.PreferencesList-based preferences:
prefs iis a full permutation ofFin n, ordered from most to least preferred.
- Used by 6
- holdinv_step
HoldInvis preserved by one DA step. Proof structure: case-analyze on the pair(s.holding p, bestNew p)that drivesdaStep's… - GS.daRun_NoAchievableRejection
NoAchievableRejectionis preserved bydaRun(threadingHoldInvand holding-injectivity, both also preserved bydaStep). - holdinv_runholdinv_run
- GS.daStep_NoAchievableRejectionInductive step (KEY LEMMA).
NoAchievableRejectionis preserved by onedaStep. Also threadsHoldInv(for the old-holder index… - holdinv_finalStateholdinv_finalState
- holdinv_initholdinv_init
- holdinv_step
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in /-- **HoldInv** (Held → Proposed): if woman `p` currently holds man `j`, then `j` must already have proposed to `p` — i.e., `p` is in the proposed-prefix `(m.prefs j).take (s.nextChoice j)` of `j`'s preference list. This is the **converse direction** of [`JInv`]: `JInv` says proposed ⇒ held; `HoldInv` says held ⇒ proposed. Together they make the two-sided correspondence between cursors and holdings airtight. `HoldInv` is the one the stability proof's "the holder must be at least as preferred as the blocker" step relies on, via `RSInv` — see the proof sketch of [`galeShapley_isStable`] and the preservation lemma [`holdinv_step`]. -/ def HoldInv (m : Preferences n) (s : DAState n) : Prop := ∀ j p : Fin n, s.holding p = some j → p ∈ (m.prefs j).take (s.nextChoice j)