GS.pref_list_mem
theoremverifiedformalizationimported Lean
Every element of Fin n appears in a full-permutation list.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in lemma GS.pref_list_mem {n : ℕ} (l : List (Fin n)) (hnd : l.Nodup) (hlen : l.length = n) (x : Fin n) : x ∈ l
- Formalizes
- EconCSLib, `GS.pref_list_mem`
- 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.GS.pref_list_mem← GS.pref_list_mem (EconCSLib/MarketDesign/Matching/GaleShapley.lean:111): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 13
- holdinv_step
HoldInvis preserved by one DA step. Proof structure: case-analyze on the pair(s.holding p, bestNew p)that drivesdaStep's… - not_free_of_nc_ge
nextChoice i ≥ n+ injectivity +JInv→ maniis not free. - GS.daStep_NoAchievableRejectionInductive step (KEY LEMMA).
NoAchievableRejectionis preserved by onedaStep. Also threadsHoldInv(for the old-holder index… - GS.joinWoman_injectiveThe join woman-assignment is injective.
- rsinv_stabilityIf j strictly prefers i over his final partner, i's final partner has rank ≤ j.
- GS.opposed_preferencesOpposed preferences. Let
μbe a stable matching. If manjis matched to womanwjunder another matchingνand **strictly… - GS.meetMan_worse_leftGS.meetMan_worse_left
- GS.joinWoman_worse_leftIf
iis the join-partner of herμ-manj, theniweakly prefers herν-man toj(sojis her worse man). - GS.opposed_preferences_womenDual of
opposed_preferences: if womanistrictly prefers manmito hercandidate-manmi', thenmistrictly prefers his… - GS.StableMatching.instPartialOrderMen-preference order:
μ ≤ νiff every man weakly prefers hisν-partner to hisμ-partner (smalleridxOf= more preferred). - 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.meetMan_injectiveGS.meetMan_injective
- holdinv_step
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 in/-- Every element of `Fin n` appears in a full-permutation list. -/lemma GS.pref_list_mem {n : ℕ} (l : List (Fin n)) (hnd : l.Nodup) (hlen : l.length = n) (x : Fin n) : x ∈ l := by rw [← List.mem_toFinset] exact (Finset.eq_univ_of_card _ (by rw [List.toFinset_card_of_nodup hnd, hlen, Fintype.card_fin])).symm ▸ Finset.mem_univ _