AFTD Auto-Formalizing Theoretical Domains

finalState_no_free_men

theoremverifiedformalizationimported Lean

At termination, every man is held (no free man remains). Proof: if a free man remained, nc_sum_grows would give n*n + 1 ≤ n*n, contradiction.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
variable (w m : Preferences n) in
lemma finalState_no_free_men :
    ∀ i : Fin n, isFree (finalState w m) i = false
Formalizes
EconCSLib, `finalState_no_free_men`
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
  • nc_sum_le_nn∑ nextChoice ≤ n * n is preserved over daRun.
  • nc_sum_growsAfter fuel rounds ending with free men, ∑ nextChoice grew by ≥ fuel.
  • GS.PreferencesList-based preferences: prefs i is a full permutation of Fin n, ordered from most to least preferred.
  • GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
  • GS.daRunRun DA for at most fuel steps, stopping early if no free men remain.
  • GS.isFreeMan i is free in s iff no woman holds him.
  • GS.finalStatefinalState: run daRun with fuel n*n + 1 from initState.
  • GS.initStateInitial state: all women free, all men start at proposal index 0.
  • JInvJInv (Proposed → Held): once man i has proposed to woman p in some prior step, p is currently held by *someone* (possibly i,…
  • jinv_initjinv_init
  • initState_injectiveinitState has trivially injective holding (all none).
  • GS.freeMenSetThe finset of all free men in s.
  • GS.mem_freeMenSetGS.mem_freeMenSet
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] invariable (w m : Preferences n) in/-- At termination, every man is held (no free man remains). Proof: if a free man remained, `nc_sum_grows` would give `n*n + 1 ≤ n*n`, contradiction. -/lemma finalState_no_free_men :    ∀ i : Fin n, isFree (finalState w m) i = false := by  intro i  -- Establish the pre-conditions for the fuel-sufficiency lemmas.  have hnc0 : ∀ j : Fin n, (initState n).nextChoice j ≤ n := by simp [initState]  have hj0 : JInv m (initState n) := jinv_init m  have hinj0 := initState_injective (n := n)  -- By contradiction: suppose some man i is still free in finalState.  by_contra hfree  simp only [Bool.not_eq_false] at hfree  -- freeMenSet (finalState w m) is nonempty.  have hne : (freeMenSet (finalState w m)).Nonempty :=    ⟨i, mem_freeMenSet.mpr hfree⟩  -- nc_sum_grows: 0 + (n*n+1) ≤ ∑ nc at finalState.  have hgrows := nc_sum_grows w m (n * n + 1) (initState n) hnc0 hj0 hinj0 hne  simp only [initState, Finset.sum_const_zero] at hgrows  -- nc_sum_le_nn: ∑ nc at finalState ≤ n*n.  have hle := nc_sum_le_nn w m (n * n + 1) (initState n) hnc0 hj0 hinj0    (by simp [initState])  -- Contradiction: n*n+1 ≤ 0 + (n*n+1) ≤ ∑ nc ≤ n*n.  simp only [initState] at hle  omega
See it in the graphDiscuss this resultChallenge it