AFTD Auto-Formalizing Theoretical Domains

single_peaked_median_defeats_less

theoremverified

Under single-peaked preferences with asymmetric preferences, if strictly more than half of the voters have peak at least 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_less {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 => m ≤ peak v) Finset.univ).card)
    (y : A) (hym : y < m) :
    (Finset.filter (fun v => P v y m) Finset.univ).card < (Finset.filter (fun v => P v m y) Finset.univ).card
Source
Black (1948), The Decisions of a Committee Using a Special Majority
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

Given a finite type $V$ of voters and a linearly ordered type $A$ of alternatives: Let $P : V \to A \to A \to \mathrm{Prop}$ be a relation such that each $P(v)$ is decidable. Assume that for all $v \in V$ and all $x, y \in A$, $P\ v\ x\ y \implies \neg P\ v\ y\ x$ (asymmetry). Let $\mathrm{peak} : V \to A$ be a function such that for all $v \in V$, $P(v)$ is single-peaked with respect to $\mathrm{peak}(v)$ (in the sense of is_single_peaked). Let $m \in A$ be an alternative such that strictly more than half of all voters have their peak greater than or equal to $m$, i.e., $|V| < 2 \cdot |\{v \in V \mid m \le \mathrm{peak}(v)\}|$. Let $y \in A$ be an alternative such that $y < m$. Then the number of voters $v \in V$ for whom $P\ v\ y\ m$ holds is strictly less than the number of voters $v \in 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 theorem is proved by a counting argument using single-peakedness and preference asymmetry. First, single-peakedness implies that every voter with peak at least $m$ strictly prefers $m$ to any alternative $y < m$, so this group of voters forms a subset of those preferring $m$ to $y$. Second, preference asymmetry ensures that the voters preferring $y$ to $m$ and those preferring $m$ to $y$ are disjoint, bounding their combined size by the total electorate. Since the voters with peak at least $m$ constitute a strict majority, those preferring $m$ to $y$ must strictly outnumber those preferring $y$ to $m$.

  1. Define the sets of voters $S_y$ (preferring $y$ to $m$), $S_m$ (preferring $m$ to $y$), and $S_{\\text{peak}}$ (having peak at least $m$).

    We enable classical reasoning and introduce abbreviations for the three relevant finite sets of voters: $S_y = \\{v \\in V \\mid P(v, y, m)\\}$, $S_m = \\{v \\in V \\mid P(v, m, y)\\}$, and $S_{\\text{peak}} = \\{v \\in V \\mid m \\le \\text{peak}(v)\\}$.

    lines 9–12

      classical
      set Sy := Finset.filter (fun v => P v y m) Finset.univ
      set Sm := Finset.filter (fun v => P v m y) Finset.univ
      set Speak := Finset.filter (fun v => m ≤ peak v) Finset.univ
  2. Every voter whose peak is at least $m$ prefers $m$ to $y$, so $S_{\\text{peak}} \\subseteq S_m$ and $|S_{\\text{peak}}| \\le |S_m|$.

    Let $v \\in S_{\\text{peak}}$, so $m \\le \\text{peak}(v)$. Given $y < m$, we have $y < m \\le \\text{peak}(v)$. By definition of single-peaked preferences (hypothesis `hsp`), whenever an alternative $m$ lies between $y$ and the voter's peak, the voter prefers $m$ to $y$. Hence $P(v, m, y)$ holds, placing $v$ in $S_m$. Since $S_{\\text{peak}} \\subseteq S_m$, monotonicity of cardinality (`Finset.card_le_card`) yields $|S_{\\text{peak}}| \\le |S_m|$.

    lines 13–20

    uses Finset.mem_filter, Finset.card_le_card

      have hsub : Speak ⊆ Sm := by
        intro v hv
        rw [Finset.mem_filter] at hv ⊢
        refine ⟨hv.1, ?_⟩
        apply hsp v y m
        left
        exact ⟨hym, hv.2⟩
      have hcard_sub : Speak.card ≤ Sm.card := Finset.card_le_card hsub
  3. The sets $S_y$ and $S_m$ are disjoint.

    By `Finset.disjoint_filter`, the two filtered sets are disjoint if no voter satisfies both conditions. If a voter $v$ prefers $y$ to $m$, the asymmetry assumption on preferences (`hasymm`) guarantees that $v$ does not prefer $m$ to $y$, so $v \\notin S_m$.

    lines 21–24

    uses Finset.disjoint_filter

      have hdisj : Disjoint Sy Sm := by
        rw [Finset.disjoint_filter]
        intro v _ hp
        exact hasymm v y m hp
  4. $|S_y| + |S_m| \\le |V|$.

    The union $S_y \\cup S_m$ is a subset of all voters $V$, so its size is at most $|V|$ by `Finset.card_le_univ`. Because $S_y$ and $S_m$ are disjoint, the size of their union equals the sum of their individual sizes (`Finset.card_union_of_disjoint`), giving $|S_y| + |S_m| \\le |V|$.

    lines 25–28

    uses Finset.card_le_univ, Finset.card_union_of_disjoint

      have hsum : Sy.card + Sm.card ≤ Fintype.card V := by
        have := Finset.card_le_univ (Sy ∪ Sm)
        rw [Finset.card_union_of_disjoint hdisj] at this
        exact this
  5. $|S_y| < |S_m|$. automation

    By hypothesis `hm`, strictly more than half of the voters have their peak at least $m$, so $|V| < 2 \\cdot |S_{\\text{peak}}|$. Combining this with $|S_{\\text{peak}}| \\le |S_m|$ gives $|V| < 2 \\cdot |S_m|$. Together with $|S_y| + |S_m| \\le |V|$, we obtain $|S_y| + |S_m| < 2 \\cdot |S_m|$, which simplifies to $|S_y| < |S_m|$. The `omega` tactic verifies this linear arithmetic over the natural numbers.

    line 29

      omega
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the filter predicate.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the cardinality of the other.
Finset.disjoint_filter
Two subsets obtained by filtering the same set with two predicates are disjoint if and only if no element satisfies both predicates simultaneously.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the total cardinality of the type.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their individual cardinalities.

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, an alternative strictly to the left of a right-majority median is majority defeated. -/theorem single_peaked_median_defeats_less {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 => m ≤ peak v) Finset.univ).card)    (y : A) (hym : y < m) :    (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 Sy := Finset.filter (fun v => P v y m) Finset.univ  set Sm := Finset.filter (fun v => P v m y) Finset.univ  set Speak := Finset.filter (fun v => m ≤ peak v) Finset.univ  have hsub : Speak ⊆ Sm := by    intro v hv    rw [Finset.mem_filter] at hv ⊢    refine ⟨hv.1, ?_⟩    apply hsp v y m    left    exact ⟨hym, hv.2⟩  have hcard_sub : Speak.card ≤ Sm.card := Finset.card_le_card hsub  have hdisj : Disjoint Sy Sm := by    rw [Finset.disjoint_filter]    intro v _ hp    exact hasymm v y m hp  have hsum : Sy.card + Sm.card ≤ Fintype.card V := by    have := Finset.card_le_univ (Sy ∪ Sm)    rw [Finset.card_union_of_disjoint hdisj] at this    exact this  omega
See it in the graphDiscuss this resultChallenge it