condorcet_balanced_top_implies_six_le_candidates
If every three-candidate set contains the top choice of at most half of the voters (and there is at least one voter and at least four candidates), then the election has at least six candidates: the balanced regime is impossible below six candidates.
Statement
theorem condorcet_balanced_top_implies_six_le_candidates (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hm : 4 ≤ m) (hbal : ∀ S : Finset (Fin m), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) : 6 ≤ m
- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- 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 proof proceeds by double counting and contradiction. The balanced condition implies that every 3-candidate subset contains the top choice of at most half of the voters, giving an upper bound on the sum of the voter counts over all triples. Conversely, counting by voter reveals that each voter's top choice appears in exactly ((m - 1).choose 2) triples, so the sum equals n * ((m - 1).choose 2). Combining the two gives the inequality 2 * ((m - 1).choose 2) ≤ m.choose 3, which fails by direct arithmetic computation when m = 4 or m = 5, forcing m ≥ 6.
Candidate 0 is valid, and we define each voter's top choice, the count of voters with top choice in a set S, and the collection T of all 3-candidate subsets.
In both the theorem hypothesis hbal (line 5) and the proof (line 7), candidate 0 is verified to be in Fin m using linear arithmetic (omega) since m ≥ 4 > 0. For each voter v, top(v) is defined as (P v)⁻¹(0). For any candidate subset S, cnt(S) counts the voters whose top choice is in S. Finally, T is defined as the set of all 3-candidate subsets of the candidates.
2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) : 6 ≤ m := by let top : Fin n → Fin m := fun v => (P v).symm ⟨0, by omega⟩ let cnt : Finset (Fin m) → ℕ := fun S => (Finset.univ.filter fun v => top v ∈ S).card let T : Finset (Finset (Fin m)) := (Finset.univ : Finset (Fin m)).powersetCard 3
For each voter v, exactly ((m - 1).choose 2) triples in T contain top(v).
Any 3-element subset containing top(v) is formed by choosing 2 additional candidates from the remaining m - 1 candidates. This is established by specializing Finset.card_filter_powersetCard_subset to the singleton {top(v)} within the universe of m candidates, rewritten via Finset.singleton_subset_iff.
uses
Finset.card_filter_powersetCard_subset,Finset.singleton_subset_iffhave hfiber (v : Fin n) : (T.filter fun S => top v ∈ S).card = (m - 1).choose 2 := by have h := Finset.card_filter_powersetCard_subset ({top v} : Finset (Fin m)) (Finset.univ : Finset (Fin m)) 3 (by simp) (by simp) simpa [T, Finset.singleton_subset_iff] using h
The sum of cnt(S) over all triples S ∈ T equals n * ((m - 1).choose 2).
We count voter-triple pairs in two ways. Express cnt(S) as a sum of 0-1 indicators via Finset.card_filter, then exchange the sums over triples S ∈ T and voters v using Finset.sum_comm. For each voter, the inner sum over S ∈ T counts triples containing top(v) via Finset.sum_boole, which equals ((m - 1).choose 2) by hfiber. Summing this constant over all n voters yields n * ((m - 1).choose 2).
uses
Finset.card_filter,Finset.sum_comm,Finset.sum_boolehave hsum : ∑ S ∈ T, cnt S = n * ((m - 1).choose 2) := by calc ∑ S ∈ T, cnt S = ∑ S ∈ T, ∑ v ∈ (Finset.univ : Finset (Fin n)), if top v ∈ S then 1 else 0 := by simp only [cnt, Finset.card_filter] _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), ∑ S ∈ T, if top v ∈ S then 1 else 0 := by rw [Finset.sum_comm] _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (T.filter fun S => top v ∈ S).card := by simp only [Finset.sum_boole] rfl _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (m - 1).choose 2 := by simp [hfiber] _ = n * ((m - 1).choose 2) := by simp
2 * ∑ S ∈ T, cnt(S) ≤ n * |T|.
Distribute the factor of 2 inside the sum over T using Finset.mul_sum. Since each S ∈ T has cardinality 3, the balanced assumption hbal guarantees that 2 * cnt(S) ≤ n for every triple S. Summing these inequalities with Finset.sum_le_sum gives at most |T| * n, which equals n * |T| by Nat.mul_comm.
uses
Finset.mul_sum,Finset.sum_le_sum,Nat.mul_commhave hle : 2 * ∑ S ∈ T, cnt S ≤ n * T.card := by calc 2 * ∑ S ∈ T, cnt S = ∑ S ∈ T, 2 * cnt S := by rw [Finset.mul_sum] _ ≤ ∑ S ∈ T, n := by apply Finset.sum_le_sum intro S hS have hScard : S.card = 3 := by simpa [T] using hS exact hbal S hScard _ = T.card * n := by simp _ = n * T.card := by rw [Nat.mul_comm]
The total number of triples is |T| = m.choose 3.
The number of 3-element subsets of an m-element set is given directly by Finset.card_powersetCard as m.choose 3.
uses
Finset.card_powersetCardhave hcardT : T.card = m.choose 3 := by simp [T, Finset.card_powersetCard]
2 * (n * ((m - 1).choose 2)) ≤ n * (m.choose 3).
Substitute the double-counting formula ∑ S ∈ T, cnt(S) = n * ((m - 1).choose 2) and the cardinality |T| = m.choose 3 into the upper bound 2 * ∑ S ∈ T, cnt(S) ≤ n * |T|.
have hineq : 2 * (n * ((m - 1).choose 2)) ≤ n * m.choose 3 := by calc 2 * (n * ((m - 1).choose 2)) = 2 * ∑ S ∈ T, cnt S := by rw [hsum] _ ≤ n * T.card := hle _ = n * m.choose 3 := by rw [hcardT]
2 * ((m - 1).choose 2) ≤ m.choose 3.
Because the number of voters n is strictly positive (hn), we can cancel the factor of n from the left of the inequality 2 * (n * ((m - 1).choose 2)) ≤ n * (m.choose 3) using Nat.le_of_mul_le_mul_left.
uses
Nat.le_of_mul_le_mul_lefthave hchoose : 2 * ((m - 1).choose 2) ≤ m.choose 3 := by apply Nat.le_of_mul_le_mul_left _ hn calc n * (2 * ((m - 1).choose 2)) = 2 * (n * ((m - 1).choose 2)) := by ring _ ≤ n * m.choose 3 := hineq
6 ≤ m. automation
Suppose for contradiction that m < 6. Since m ≥ 4, the only remaining possibilities are m = 4 and m = 5. In both cases, the inequality 2 * ((m - 1).choose 2) ≤ m.choose 3 is violated: for m = 4 it gives 6 ≤ 4, and for m = 5 it gives 12 ≤ 10. Evaluating the binomial coefficients (Nat.choose) closes each case and produces a contradiction.
uses
Nat.chooseby_contra h6 have hmlt : m < 6 := by omega interval_cases m <;> norm_num [Nat.choose] at hchoose
Finset.card_filter_powersetCard_subset- The number of n-element subsets of t containing a given subset s ⊆ t is ((|t| - |s|).choose (n - |s|)).
Finset.singleton_subset_iff- A singleton set {a} is a subset of s if and only if a ∈ s.
Finset.card_filter- The cardinality of a filtered subset equals the sum of its boolean indicator values over the whole set.
Finset.sum_comm- Swapping the order of summation in a finite double sum does not change the result.
Finset.sum_boole- The sum of an indicator condition over a finite set equals the cardinality of the subset satisfying the condition.
Finset.mul_sum- A scalar factor distributes over a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Finset.card_powersetCard- The number of subsets of size n of a finite set s is (|s|.choose n).
Nat.le_of_mul_le_mul_left- A positive multiplier c can be cancelled from the left of an inequality: c * a ≤ c * b implies a ≤ b when c > 0.
Nat.choose- The binomial coefficient function on natural numbers.
- Candidate 0 is represented as a bounded index ⟨0, by omega⟩ in Fin m, which is well-defined because m ≥ 4 > 0.
- Step 8 uses numeric evaluation (norm_num) to refute the finite cases m = 4 and m = 5 by arithmetic.
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.
/-- The balanced case of the Condorcet-dimension problem cannot occur with at most five candidates. -/theorem condorcet_balanced_top_implies_six_le_candidates (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hm : 4 ≤ m) (hbal : ∀ S : Finset (Fin m), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) : 6 ≤ m := by let top : Fin n → Fin m := fun v => (P v).symm ⟨0, by omega⟩ let cnt : Finset (Fin m) → ℕ := fun S => (Finset.univ.filter fun v => top v ∈ S).card let T : Finset (Finset (Fin m)) := (Finset.univ : Finset (Fin m)).powersetCard 3 have hfiber (v : Fin n) : (T.filter fun S => top v ∈ S).card = (m - 1).choose 2 := by have h := Finset.card_filter_powersetCard_subset ({top v} : Finset (Fin m)) (Finset.univ : Finset (Fin m)) 3 (by simp) (by simp) simpa [T, Finset.singleton_subset_iff] using h have hsum : ∑ S ∈ T, cnt S = n * ((m - 1).choose 2) := by calc ∑ S ∈ T, cnt S = ∑ S ∈ T, ∑ v ∈ (Finset.univ : Finset (Fin n)), if top v ∈ S then 1 else 0 := by simp only [cnt, Finset.card_filter] _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), ∑ S ∈ T, if top v ∈ S then 1 else 0 := by rw [Finset.sum_comm] _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (T.filter fun S => top v ∈ S).card := by simp only [Finset.sum_boole] rfl _ = ∑ v ∈ (Finset.univ : Finset (Fin n)), (m - 1).choose 2 := by simp [hfiber] _ = n * ((m - 1).choose 2) := by simp have hle : 2 * ∑ S ∈ T, cnt S ≤ n * T.card := by calc 2 * ∑ S ∈ T, cnt S = ∑ S ∈ T, 2 * cnt S := by rw [Finset.mul_sum] _ ≤ ∑ S ∈ T, n := by apply Finset.sum_le_sum intro S hS have hScard : S.card = 3 := by simpa [T] using hS exact hbal S hScard _ = T.card * n := by simp _ = n * T.card := by rw [Nat.mul_comm] have hcardT : T.card = m.choose 3 := by simp [T, Finset.card_powersetCard] have hineq : 2 * (n * ((m - 1).choose 2)) ≤ n * m.choose 3 := by calc 2 * (n * ((m - 1).choose 2)) = 2 * ∑ S ∈ T, cnt S := by rw [hsum] _ ≤ n * T.card := hle _ = n * m.choose 3 := by rw [hcardT] have hchoose : 2 * ((m - 1).choose 2) ≤ m.choose 3 := by apply Nat.le_of_mul_le_mul_left _ hn calc n * (2 * ((m - 1).choose 2)) = 2 * (n * ((m - 1).choose 2)) := by ring _ ≤ n * m.choose 3 := hineq by_contra h6 have hmlt : m < 6 := by omega interval_cases m <;> norm_num [Nat.choose] at hchoose