single_peaked_median_defeats_less
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
- single_peaked_median_is_condorcet_winnerUnder single-peaked preferences with asymmetric preferences, if an alternative m satisfies that strictly more than half of the voters have…
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$.
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)\\}$.
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
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|$.
uses
Finset.mem_filter,Finset.card_le_cardhave 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
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$.
uses
Finset.disjoint_filterhave hdisj : Disjoint Sy Sm := by rw [Finset.disjoint_filter] intro v _ hp exact hasymm v y m hp
$|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|$.
uses
Finset.card_le_univ,Finset.card_union_of_disjointhave 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
$|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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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