AFTD Auto-Formalizing Theoretical Domains

single_peaked_median_defeats_greater

theoremverified

Under single-peaked preferences with asymmetric preferences, if strictly more than half of the voters have peak at most m, then for any alternative y > m, the number of voters preferring y to m is strictly less than the number preferring m to y.

Statement

theorem single_peaked_median_defeats_greater {V A : Type*} [Fintype V] [LinearOrder A]
    (P : V → A → A → Prop) [∀ v, DecidableRel (P v)]
    (hasymm : ∀ v x y, P v x y → ¬ P v y x)
    (peak : V → A) (hsp : ∀ v, is_single_peaked (P v) (peak v))
    (m : A) (hm : Fintype.card V < 2 * (Finset.filter (fun v => peak v ≤ m) Finset.univ).card)
    (y : A) (hym : m < y) :
    (Finset.filter (fun v => P v y m) Finset.univ).card < (Finset.filter (fun v => P v m y) Finset.univ).card
Source
Duncan Black, 'On the Rationale of Group Decision-making', Journal of Political Economy 56(1):23-34 (1948)
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_single_peakedA strict preference relation P over a linearly ordered set of alternatives A is single-peaked with peak p if moving toward p strictly…
Used by 1

Read back from the Lean

Let V be a finite type (representing voters) and A a linearly ordered type (representing alternatives). Let P : V → A → A → Prop be a binary relation on A for each v : V, with P v decidable for all v. Assume that for all v : V and all x, y : A, P v x y implies ¬ P v y x (asymmetry). Let peak : V → A be a function such that for every voter v : V, P v is single-peaked at peak v (in the sense of is_single_peaked). Let m : A be an alternative such that strictly more than half of all voters have their peak less than or equal to m (specifically, Fintype.card V < 2 * |{v : V | peak v ≤ m}|). Let y : A be an alternative strictly greater than m (m < y). Then the number of voters v : V for whom P v y m holds is strictly less than the number of voters v : V for whom P v m y holds.

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

The proof, explained

The proof compares the number of voters who prefer y to m with those who prefer m to y by focusing on the majority S of voters whose peak is at most m. By single-peakedness, every voter in S prefers m to y, meaning S is a subset of the voters preferring m to y and is disjoint from the voters preferring y to m. Since these two groups are disjoint subsets of all voters, their combined cardinality cannot exceed the total population; combined with the fact that S contains strictly more than half of all voters, this forces strictly fewer voters to prefer y over m than prefer m over y.

  1. Define the three relevant subsets of voters: S (peaks at most m), M (preferring m to y), and Y (preferring y to m).

    Assuming classical logic, we introduce names for three subsets of the finite voter set V: S = {v ∈ V | peak(v) ≤ m}, M = {v ∈ V | P v m y}, and Y = {v ∈ V | P v y m}.

    lines 9–12

      classical
      set S := Finset.filter (fun v => peak v ≤ m) Finset.univ
      set M := Finset.filter (fun v => P v m y) Finset.univ
      set Y := Finset.filter (fun v => P v y m) Finset.univ
  2. S ⊆ M, and consequently |S| ≤ |M|.

    Take any voter v ∈ S, so peak(v) ≤ m. Since m < y, the peak lies to the left of both m and y (peak(v) ≤ m < y). By the single-peakedness hypothesis (hsp), voter v prefers m to y, so v ∈ M. Thus S ⊆ M, which implies |S| ≤ |M| by monotonicity of cardinality (Finset.card_le_card).

    lines 13–20

    uses Finset.mem_filter, Finset.card_le_card

      have hSM : S ⊆ M := by
        intro v hv
        rw [Finset.mem_filter] at hv ⊢
        refine ⟨hv.1, ?_⟩
        apply hsp v y m
        right
        exact ⟨hv.2, hym⟩
      have hS_card : S.card ≤ M.card := Finset.card_le_card hSM
  3. The subsets Y and S are disjoint.

    By Finset.disjoint_left, it suffices to show that no voter belongs to both Y and S. If v ∈ S, single-peakedness implies that v prefers m to y (P v m y). If v ∈ Y, then v prefers y to m (P v y m). But preferences are asymmetric (hasymm), so both cannot hold simultaneously.

    lines 21–29

    uses Finset.disjoint_left, Finset.mem_filter

      have hdisj : Disjoint Y S := by
        rw [Finset.disjoint_left]
        intro v hvY hvS
        rw [Finset.mem_filter] at hvY hvS
        have hPmy : P v m y := by
          apply hsp v y m
          right
          exact ⟨hvS.2, hym⟩
        exact hasymm v m y hPmy hvY.2
  4. |Y| + |S| ≤ |V|.

    Because Y and S are disjoint, the cardinality of their union is |Y| + |S| by Finset.card_union_of_disjoint. Since Y ∪ S is a subset of all voters V (Finset.subset_univ), its cardinality is at most |V| by Finset.card_le_card and Finset.card_univ.

    lines 30–36

    uses Finset.subset_univ, Finset.card_union_of_disjoint, Finset.card_le_card, Finset.card_univ

      have hle : Y.card + S.card ≤ Fintype.card V := by
        have hsub : Y ∪ S ⊆ Finset.univ := Finset.subset_univ (Y ∪ S)
        have hunion := Finset.card_union_of_disjoint hdisj
        have hcard := Finset.card_le_card hsub
        rw [hunion] at hcard
        rw [Finset.card_univ] at hcard
        exact hcard
  5. |Y| < |M|. automation

    The goal is to show |Y| < |M|. We know that |Y| + |S| ≤ |V|, that |V| < 2 * |S| by the majority hypothesis (hm), and that |S| ≤ |M|. Together, these inequalities force |Y| < |S| ≤ |M|, which the omega tactic establishes via Presburger arithmetic.

    lines 37–39

      change Y.card < M.card
      have hm' : Fintype.card V < 2 * S.card := hm
      omega
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the predicate.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most that of the superset.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ
The cardinality of the universal set of a finite type equals the cardinality of that type.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Under single-peaked preferences, if strictly more than half of voters have peak at most m, then for any y > m strictly fewer voters prefer y to m than prefer m to y. -/theorem single_peaked_median_defeats_greater {V A : Type*} [Fintype V] [LinearOrder A]    (P : V → A → A → Prop) [∀ v, DecidableRel (P v)]    (hasymm : ∀ v x y, P v x y → ¬ P v y x)    (peak : V → A) (hsp : ∀ v, is_single_peaked (P v) (peak v))    (m : A) (hm : Fintype.card V < 2 * (Finset.filter (fun v => peak v ≤ m) Finset.univ).card)    (y : A) (hym : m < y) :    (Finset.filter (fun v => P v y m) Finset.univ).card < (Finset.filter (fun v => P v m y) Finset.univ).card := by  classical  set S := Finset.filter (fun v => peak v ≤ m) Finset.univ  set M := Finset.filter (fun v => P v m y) Finset.univ  set Y := Finset.filter (fun v => P v y m) Finset.univ  have hSM : S ⊆ M := by    intro v hv    rw [Finset.mem_filter] at hv ⊢    refine ⟨hv.1, ?_⟩    apply hsp v y m    right    exact ⟨hv.2, hym⟩  have hS_card : S.card ≤ M.card := Finset.card_le_card hSM  have hdisj : Disjoint Y S := by    rw [Finset.disjoint_left]    intro v hvY hvS    rw [Finset.mem_filter] at hvY hvS    have hPmy : P v m y := by      apply hsp v y m      right      exact ⟨hvS.2, hym⟩    exact hasymm v m y hPmy hvY.2  have hle : Y.card + S.card ≤ Fintype.card V := by    have hsub : Y ∪ S ⊆ Finset.univ := Finset.subset_univ (Y ∪ S)    have hunion := Finset.card_union_of_disjoint hdisj    have hcard := Finset.card_le_card hsub    rw [hunion] at hcard    rw [Finset.card_univ] at hcard    exact hcard  change Y.card < M.card  have hm' : Fintype.card V < 2 * S.card := hm  omega
See it in the graphDiscuss this resultChallenge it