AFTD Auto-Formalizing Theoretical Domains

HoldInv

defimported Lean

HoldInv (Held → Proposed): if woman p currently holds man j, then j must already have proposed to p — i.e., p is in the proposed-prefix (m.prefs j).take (s.nextChoice j) of j's preference list. This is the converse direction of [JInv]: JInv says proposed ⇒ held; HoldInv says held ⇒ proposed. Together they make the two-sided correspondence between cursors and holdings airtight. HoldInv is the one the stability proof's "the holder must be at least as preferred as the blocker" step relies on, via RSInv — see the proof sketch of [galeShapley_isStable] and the preservation lemma [holdinv_step].

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open List Finset in
open GS in
variable {n : ℕ} [NeZero n] in
def HoldInv (m : Preferences n) (s : DAState n) : Prop
Defined in
EconCSLib, `HoldInv`
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 6

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
/-- **HoldInv** (Held → Proposed): if woman `p` currently holds man `j`, then `j` must already have proposed to `p` — i.e., `p` is in the proposed-prefix `(m.prefs j).take (s.nextChoice j)` of `j`'s preference list. This is the **converse direction** of [`JInv`]: `JInv` says proposed ⇒ held; `HoldInv` says held ⇒ proposed. Together they make the two-sided correspondence between cursors and holdings airtight. `HoldInv` is the one the stability proof's "the holder must be at least as preferred as the blocker" step relies on, via `RSInv` — see the proof sketch of [`galeShapley_isStable`] and the preservation lemma [`holdinv_step`]. -/
def HoldInv (m : Preferences n) (s : DAState n) : Prop :=
  ∀ j p : Fin n, s.holding p = some j → p ∈ (m.prefs j).take (s.nextChoice j)
See it in the graphDiscuss this resultChallenge it