AFTD Auto-Formalizing Theoretical Domains

JInv

defimported Lean

JInv (Proposed → Held): once man i has proposed to woman p in some prior step, p is currently held by *someone* (possibly i, possibly someone better). Formally: every p in the prefix (m.prefs i).take (s.nextChoice i) of i's preference list — i.e., every woman i has already proposed to — has s.holding p = some _. This is the "once proposed-to, always held" invariant: a woman who has ever received a proposal can never go back to being unmatched. It is the dual of [HoldInv] (every currently-held woman is in her holder's proposed prefix), which gives the converse direction. Together JInv and HoldInv pin down a bidirectional correspondence between the per-man cursors and the per-woman holdings, which the stability proof needs in both directions.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
def JInv (m : Preferences n) (s : DAState n) : Prop
Defined in
EconCSLib, `JInv`
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
none listed
Built on 2
  • GS.DAStateDA state: per-man proposal cursor + per-woman tentative hold.
  • GS.PreferencesList-based preferences: prefs i is a full permutation of Fin n, ordered from most to least preferred.
Used by 10

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
/-- **JInv** (Proposed → Held): once man `i` has proposed to woman `p` in some prior step, `p` is currently held by *someone* (possibly `i`, possibly someone better). Formally: every `p` in the prefix `(m.prefs i).take (s.nextChoice i)` of `i`'s preference list — i.e., every woman `i` has already proposed to — has `s.holding p = some _`. This is the **"once proposed-to, always held"** invariant: a woman who has ever received a proposal can never go back to being unmatched. It is the dual of [`HoldInv`] (every currently-held woman is in her holder's proposed prefix), which gives the converse direction. Together `JInv` and `HoldInv` pin down a bidirectional correspondence between the per-man cursors and the per-woman holdings, which the stability proof needs in both directions. -/
def JInv (m : Preferences n) (s : DAState n) : Prop :=
  ∀ i p : Fin n, p ∈ (m.prefs i).take (s.nextChoice i) → ∃ h : Fin n, s.holding p = some h
See it in the graphDiscuss this resultChallenge it