AFTD Auto-Formalizing Theoretical Domains

stable_matching_of_subsingleton

theoremverifiedformalization

In a marriage market market with agent types M and W where M is a subsingleton (Subsingleton M), if men's preferences are irreflexive (∀ (m : M) (w : W), ¬ market.pref_m m w w), then any matching equivalence μ : M ≃ W has no blocking pairs, meaning that for all m : M and w : W, ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w)).

Statement

theorem stable_matching_of_subsingleton {M W : Type*} [Subsingleton M] (market : MarriageMarket M W) (h_irrefl : ∀ (m : M) (w : W), ¬ market.pref_m m w w) (μ : M ≃ W) : ∀ (m : M) (w : W), ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w))
Formalizes
standard textbook observation (matching markets: with at most one man and irreflexive preferences every matching is stable); folklore
Verified
06 Oct 2026
Axioms
Quot.sound
Built on 1
  • MarriageMarketA marriage market with types M and W consists of a relation pref_m : M → W → W → Prop representing men's preferences over women, and a…

Read back from the Lean

Let M and W be types, with M assumed to be a subsingleton (having at most one element). Let market be a marriage market on M and W (with men's preference relation market.pref_m and women's preference relation market.pref_w). Assume h_irrefl: for every man m : M and woman w : W, m does not prefer w to w (¬ market.pref_m m w w). Then for any bijection (equivalence) μ : M ≃ W, μ has no blocking pairs: for every m : M and w : W, it is not the case that both m prefers w to his partner μ m (market.pref_m m w (μ m)) and w prefers m to her partner μ.symm w (market.pref_w w m (μ.symm w)).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- In a subsingleton marriage market with irreflexive preferences, every matching is stable. -/theorem stable_matching_of_subsingleton {M W : Type*} [Subsingleton M] (market : MarriageMarket M W) (h_irrefl : ∀ (m : M) (w : W), ¬ market.pref_m m w w) (μ : M ≃ W) : ∀ (m : M) (w : W), ¬ (market.pref_m m w (μ m) ∧ market.pref_w w m (μ.symm w)) := by  intro m w ⟨h1, _⟩  have : Subsingleton W := μ.symm.subsingleton  have hw : w = μ m := Subsingleton.elim w (μ m)  subst hw  exact h_irrefl m (μ m) h1
See it in the graphDiscuss this resultChallenge it