not_free_of_nc_ge
theoremverifiedformalizationimported Lean
nextChoice i ≥ n + injectivity + JInv → man i is not free.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open List Finset in open GS in variable {n : ℕ} [NeZero n] in lemma not_free_of_nc_ge (m : Preferences n) (s : DAState n) (i : Fin n) (hj : JInv m s) (hinj : ∀ j1 j2 k : Fin n, s.holding j1 = some k → s.holding j2 = some k → j1 = j2) (hnc : n ≤ s.nextChoice i) : isFree s i = false
- Formalizes
- EconCSLib, `not_free_of_nc_ge`
- 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.not_free_of_nc_ge← not_free_of_nc_ge (EconCSLib/MarketDesign/Matching/GaleShapley.lean:546): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- GS.isFreeMan
iis free insiff no woman holds him. - GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
- JInvJInv (Proposed → Held): once man
ihas proposed to womanpin some prior step,pis currently held by *someone* (possiblyi,… - GS.PreferencesList-based preferences:
prefs iis a full permutation ofFin n, ordered from most to least preferred. - GS.pref_list_memEvery element of
Fin nappears in a full-permutation list. - GS.not_isFree_iffGS.not_isFree_iff
- GS.isFreeMan
- Used by 1
- daStep_nc_le_n
nextChoice i ≤ nfordaStep.
- daStep_nc_le_n
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/-- `nextChoice i ≥ n` + injectivity + `JInv` → man `i` is not free. -/lemma not_free_of_nc_ge (m : Preferences n) (s : DAState n) (i : Fin n) (hj : JInv m s) (hinj : ∀ j1 j2 k : Fin n, s.holding j1 = some k → s.holding j2 = some k → j1 = j2) (hnc : n ≤ s.nextChoice i) : isFree s i = false := by rw [not_isFree_iff] have hall : ∀ j : Fin n, ∃ h, s.holding j = some h := by intro j apply hj i j have hmem : j ∈ m.prefs i := pref_list_mem _ (m.valid i).1 (m.valid i).2 j rw [List.take_of_length_le (by rw [(m.valid i).2]; exact hnc)] exact hmem -- The function j ↦ (hall j).choose is injective (by holding injectivity), -- hence surjective on the finite type Fin n. let f : Fin n → Fin n := fun j => (hall j).choose have hfinj : Function.Injective f := by intro j1 j2 heq exact hinj j1 j2 (hall j1).choose (hall j1).choose_spec (show s.holding j2 = some (f j1) from heq ▸ (hall j2).choose_spec) have hfsurj : Function.Surjective f := Finite.injective_iff_surjective.mp hfinj obtain ⟨j, rfl⟩ := hfsurj i exact ⟨j, (hall j).choose_spec⟩