AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • GS.isFreeMan i is free in s iff no woman holds him.
  • GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
  • JInvJInv (Proposed → Held): once man i has proposed to woman p in some prior step, p is currently held by *someone* (possibly i,…
  • GS.PreferencesList-based preferences: prefs i is a full permutation of Fin n, ordered from most to least preferred.
  • GS.pref_list_memEvery element of Fin n appears in a full-permutation list.
  • GS.not_isFree_iffGS.not_isFree_iff
Used by 1

Lean source view module on GitHub

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⟩
See it in the graphDiscuss this resultChallenge it