condorcet_dimension_le_three_of_le_four
Every election with at most four candidates (and at least one voter) has a Condorcet winning set of at most three candidates: drop a candidate ranked first by fewer than half of the voters.
Statement
theorem condorcet_dimension_le_three_of_le_four (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
(hn : 0 < n) (hm : m ≤ 4) :
∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S- Related work
- smallest nontrivial case of the question whether the Condorcet dimension is always at most 3 (Condorcet winning sets (Social Choice and Welfare 44(3):493-517, 2015); arXiv:2604.19851 states the gap 3 ≤ dim ≤ 5 as open)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
- condorcet_winning_set_univThe set of all candidates is a Condorcet winning set.
- Used by 1
- condorcet_dimension_le_three_of_le_fiveEvery election with at most 5 candidates (and at least 1 voter) has a Condorcet winning set of at most 3 candidates.
The proof, explained
The theorem is proved by case analysis on the number of candidates m ≤ 4. If m < 4, taking all candidates gives a winning set of size at most three. When m = 4, the sets of voters ranking each candidate first are pairwise disjoint, so their sizes sum to at most n. Since n > 0, an averaging argument guarantees some candidate a is ranked first by strictly fewer than n/2 voters. Dropping candidate a leaves three candidates, and because a cannot defeat all three simultaneously by a majority, the remaining three form a Condorcet winning set.
If there are strictly fewer than four candidates (m < 4), the full set of candidates is a Condorcet winning set of size at most three.
We split into cases using `Nat.lt_or_ge` on whether m < 4 or m ≥ 4. If m < 4, the full set of candidates Finset.univ has size m ≤ 3. By `condorcet_winning_set_univ`, the full candidate set is always a Condorcet winning set because no candidate is left outside the set, which closes this case.
uses
Nat.lt_or_ge,condorcet_winning_set_univclassical rcases Nat.lt_or_ge m 4 with hm3 | hm4 · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩
In the remaining case, the number of candidates is exactly four (m = 4).
Since m ≤ 4 by hypothesis and m ≥ 4 from the case split, linear integer arithmetic (`omega`) determines that m = 4.
obtain rfl : m = 4 := by omega
For each candidate a, the set top(a) of voters who rank a strictly ahead of all other candidates is well-defined, and these sets are pairwise disjoint across all four candidates.
For each candidate a, top(a) is defined as the set of voters v who rank a strictly ahead of every other candidate b ≠ a (using `Finset.mem_filter`). To prove pairwise disjointness (`Function.onFun`, `Finset.disjoint_left`), suppose for contradiction that some voter v belongs to both top(a) and top(b) with a ≠ b (`Ne.symm`, `Finset.mem_univ`). Then v ranks a ahead of b and b ahead of a, so P(v)(a) < P(v)(b) < P(v)(a). By transitivity this gives P(v)(a) < P(v)(a), contradicting the irreflexivity of strict inequality (`lt_irrefl`).
uses
Function.onFun,Finset.disjoint_left,Finset.mem_filter,Ne.symm,Finset.mem_univ,lt_irrefllet top : Fin 4 → Finset (Fin n) := fun a => Finset.univ.filter fun v => ∀ b ∈ Finset.univ.erase a, P v a < P v b have hdisj : (↑(Finset.univ : Finset (Fin 4)) : Set (Fin 4)).PairwiseDisjoint top := by intro a _ b _ hab rw [Function.onFun, Finset.disjoint_left] intro v hva hvb simp only [top, Finset.mem_filter] at hva hvb have h1 := hva.2 b (Finset.mem_erase.2 ⟨Ne.symm hab, Finset.mem_univ _⟩) have h2 := hvb.2 a (Finset.mem_erase.2 ⟨hab, Finset.mem_univ _⟩) exact absurd (h1.trans h2) (lt_irrefl _)
The sum of the numbers of voters ranking each candidate first is at most the total number of voters n.
Because the sets top(a) are pairwise disjoint, the sum of their cardinalities equals the size of their union (`Finset.card_biUnion`). This union is a subset of all n voters, so its cardinality is bounded by n (`Finset.card_le_univ`).
uses
Finset.card_biUnion,Finset.card_le_univhave hsum : ∑ a, (top a).card ≤ n := by rw [← Finset.card_biUnion hdisj] exact (Finset.card_le_univ _).trans (by simp)
There exists a candidate a ranked first by strictly fewer than n / 2 voters, that is, 2 * |top(a)| < n.
Suppose for contradiction that every candidate a satisfies 2 * |top(a)| ≥ n. Summing over all four candidates (`Finset.sum_le_sum`) and distributing the multiplication (`Finset.mul_sum`, `Finset.sum_const`, `Finset.card_univ`, `Fintype.card_fin`, `smul_eq_mul`) gives 4n ≤ 2 ∑_a |top(a)|. Since the sum of cardinalities is at most n, this yields 4n ≤ 2n. Because n > 0, this is impossible (`omega`).
uses
Finset.sum_le_sum,Finset.mul_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mulobtain ⟨a, ha⟩ : ∃ a, 2 * (top a).card < n := by by_contra h push Not at h have h4 : ∑ _a : Fin 4, n ≤ ∑ a, 2 * (top a).card := Finset.sum_le_sum fun a _ => h a rw [← Finset.mul_sum] at h4 simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h4 omega
Removing candidate a leaves a set of at most three candidates that forms a Condorcet winning set.
We choose S to be all candidates except a, namely Finset.univ.erase a. Its size is 4 - 1 = 3 ≤ 3. By definition, S is a Condorcet winning set if no candidate outside S is preferred to every member of S by at least half the voters. The only candidate not in S is x = a. The voters preferring a to all candidates in S are precisely those who rank a first, namely top(a). Since 2 * |top(a)| < n by choice of a, strictly fewer than half the voters prefer a to all of S, so S is a Condorcet winning set.
refine ⟨Finset.univ.erase a, by simp, fun x hx => ?_⟩ have : x = a := by simpa using hx subst this exact ha
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
condorcet_winning_set_univ- The set of all candidates is always a Condorcet winning set.
Function.onFun- Applies a binary relation to the results of a function on two arguments: Function.onFun R f x y = R (f x) (f y).
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter- An element belongs to a filtered finset s.filter p if and only if it belongs to s and satisfies predicate p.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_univ- Every element of a finite type belongs to its universe finset Finset.univ.
lt_irrefl- Strict inequality is irreflexive: for any element a, ¬(a < a).
Finset.card_biUnion- The cardinality of a union of pairwise disjoint finite sets indexed by a finset equals the sum of their cardinalities.
Finset.card_le_univ- The cardinality of any sub-finset of a finite type is at most the total cardinality of that type.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finset s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
Finset.mul_sum- Multiplication distributes over finite summation: a * ∑ i ∈ s, f(i) = ∑ i ∈ s, a * f(i).
Finset.sum_const- The sum of a constant value b over a finset s equals |s| • b.
Finset.card_univ- The cardinality of the universe finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
smul_eq_mul- Scalar multiplication of natural numbers coincides with ordinary multiplication.
- In this formalization, a voter v's preference is represented by a permutation P(v) of candidates where a smaller numerical value indicates a higher preference rank; thus P(v)(a) < P(v)(b) means voter v prefers candidate a over candidate b.
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.
theorem condorcet_dimension_le_three_of_le_four (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hm : m ≤ 4) : ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by classical rcases Nat.lt_or_ge m 4 with hm3 | hm4 · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩ obtain rfl : m = 4 := by omega let top : Fin 4 → Finset (Fin n) := fun a => Finset.univ.filter fun v => ∀ b ∈ Finset.univ.erase a, P v a < P v b have hdisj : (↑(Finset.univ : Finset (Fin 4)) : Set (Fin 4)).PairwiseDisjoint top := by intro a _ b _ hab rw [Function.onFun, Finset.disjoint_left] intro v hva hvb simp only [top, Finset.mem_filter] at hva hvb have h1 := hva.2 b (Finset.mem_erase.2 ⟨Ne.symm hab, Finset.mem_univ _⟩) have h2 := hvb.2 a (Finset.mem_erase.2 ⟨hab, Finset.mem_univ _⟩) exact absurd (h1.trans h2) (lt_irrefl _) have hsum : ∑ a, (top a).card ≤ n := by rw [← Finset.card_biUnion hdisj] exact (Finset.card_le_univ _).trans (by simp) obtain ⟨a, ha⟩ : ∃ a, 2 * (top a).card < n := by by_contra h push Not at h have h4 : ∑ _a : Fin 4, n ≤ ∑ a, 2 * (top a).card := Finset.sum_le_sum fun a _ => h a rw [← Finset.mul_sum] at h4 simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h4 omega refine ⟨Finset.univ.erase a, by simp, fun x hx => ?_⟩ have : x = a := by simpa using hx subst this exact ha