AFTD Auto-Formalizing Theoretical Domains

GS.joinWoman_injective

theoremverifiedformalizationimported Lean

The join woman-assignment is injective.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open GS in
variable {n : ℕ} (w m : Preferences n) in
variable {w m} in
variable (μ ν : Matching (Fin n) (Fin n))
  (hμ : Matching.IsStable (MatchingMarket.ofEquivData w m) μ)
  (hν : Matching.IsStable (MatchingMarket.ofEquivData w m) ν) in
lemma GS.joinWoman_injective : Function.Injective (joinWoman μ ν hμ hν)
Formalizes
EconCSLib, `GS.joinWoman_injective`
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 13
Used by 1
  • GS.joinEquivThe join woman-assignment packaged as an equivalence (injective on the finite Fin n, hence bijective).

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen GS invariable {n : ℕ} (w m : Preferences n) invariable {w m} invariable (μ ν : Matching (Fin n) (Fin n))  (hμ : Matching.IsStable (MatchingMarket.ofEquivData w m) μ)  (hν : Matching.IsStable (MatchingMarket.ofEquivData w m) ν) in/-- The join woman-assignment is injective. -/lemma GS.joinWoman_injective : Function.Injective (joinWoman μ ν hμ hν) := by  intro j1 j2 he  set i := joinWoman μ ν hμ hν j1 with hidef  have h1 : joinWoman μ ν hμ hν j1 = i := hidef.symm  have h2 : joinWoman μ ν hμ hν j2 = i := he.symm.trans hidef.symm  rcases joinWoman_mem_men μ ν hμ hν h1 with hm1 | hn1 <;>    rcases joinWoman_mem_men μ ν hμ hν h2 with hm2 | hn2  · exact hm1.symm.trans hm2          -- both μ-men of i  · -- j1 = μ-man, j2 = ν-man    have a := joinWoman_worse_left μ ν hμ hν h1 hm1   -- idxOf (mPartner ν i) ≤ idxOf j1    have b := joinWoman_worse_right μ ν hμ hν h2 hn2  -- idxOf (mPartner μ i) ≤ idxOf j2    rw [hn2] at a; rw [hm1] at b    exact (List.idxOf_inj (pref_list_mem _ (w.valid i).1 (w.valid i).2 j1)).mp      (le_antisymm b a)  · -- j1 = ν-man, j2 = μ-man    have a := joinWoman_worse_right μ ν hμ hν h1 hn1  -- idxOf (mPartner μ i) ≤ idxOf j1    have b := joinWoman_worse_left μ ν hμ hν h2 hm2   -- idxOf (mPartner ν i) ≤ idxOf j2    rw [hm2] at a; rw [hn1] at b    exact (List.idxOf_inj (pref_list_mem _ (w.valid i).1 (w.valid i).2 j1)).mp      (le_antisymm b a)  · exact hn1.symm.trans hn2          -- both ν-men of i
See it in the graphDiscuss this resultChallenge it