single_peaked_median_defeats_greater
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
- 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
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.
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}.
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
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).
uses
Finset.mem_filter,Finset.card_le_cardhave 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
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.
uses
Finset.disjoint_left,Finset.mem_filterhave 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
|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.
uses
Finset.subset_univ,Finset.card_union_of_disjoint,Finset.card_le_card,Finset.card_univhave 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
|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.
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
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, 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