condorcet_six_balanced_top_structure
With six candidates, if every three-candidate set contains the top choice of at most half of the voters, then the top-choice profile is completely rigid: every candidate is the top choice of exactly n/6 voters.
Statement
theorem condorcet_six_balanced_top_structure (n : ℕ) (P : Fin n → Equiv.Perm (Fin 6)) (hbal : ∀ S : Finset (Fin 6), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) : ∀ c : Fin 6, 6 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ = c).card = n
- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_six_balanced_has_winning_three_setOpen sub-problem: every six-candidate election with at least one voter in which every three-candidate set contains the top choice of at…
The proof, explained
The proof shows that if every 3-candidate subset contains the top choice of at most half the voters, then the top-choice profile is uniform. Since the voters partition among the candidates according to their top choices, the sum of all top-choice counts is n. For any 3-candidate subset, both the set and its complement have size 3 and each can contain at most n/2 top choices, which forces every 3-candidate set to contain exactly n/2 top choices. Swapping one candidate for another between two overlapping triples proves that all six candidate counts must be identical, and since six equal non-negative integers sum to n, each candidate receives exactly n/6 top choices.
Establish the top-choice representation, candidate voter counts t(c), and restate the balance hypothesis.
The arithmetic condition 0 < 6 needed to construct the first-rank position ⟨0, _⟩ : Fin 6 is checked inline by norm_num in the theorem statement. Within the proof, we assume classical logic and define top(v) as voter v's top-ranked candidate (P v).symm ⟨0, _⟩, fib(c) as the fiber of voters with top choice c, and t(c) as the cardinality of this fiber. The balance hypothesis hbal is then restated as hbal' using top.
2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) : ∀ c : Fin 6, 6 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ = c).card = n := by classical let top : Fin n → Fin 6 := fun v => (P v).symm ⟨0, by norm_num⟩ let fib : Fin 6 → Finset (Fin n) := fun c => Finset.univ.filter fun v => top v = c let t : Fin 6 → ℕ := fun c => (fib c).card have hbal' : ∀ S : Finset (Fin 6), S.card = 3 → 2 * (Finset.univ.filter fun v => top v ∈ S).card ≤ n := hbal
The sum of top-choice counts across all six candidates is n: ∑ c, t c = n.
Every voter has exactly one top choice, partitioning the n voters into the fibers of the top-choice map. By Finset.card_eq_sum_card_fiberwise, the total number of voters n equals the sum of the fiber sizes ∑ c, t c.
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fintype.card_finhave hsum : ∑ c : Fin 6, t c = n := by have h := Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := top) (by intro a _; simp) simp only [Finset.card_univ, Fintype.card_fin] at h rw [← h]
For any set of candidates S, the number of voters whose top choice lies in S equals ∑ c ∈ S, t c.
The set of voters with top choice in S is the union of fibers fib(c) for c ∈ S. Since voters have a unique top choice, these fibers are pairwise disjoint, so Finset.card_biUnion shows the cardinality of the union equals the sum of the cardinalities t c.
uses
Function.onFun,Finset.disjoint_left,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_biUnion,Finset.card_biUnionhave htop_card : ∀ S : Finset (Fin 6), (Finset.univ.filter fun v => top v ∈ S).card = ∑ c ∈ S, t c := by intro S have hdisj : (↑S : Set (Fin 6)).PairwiseDisjoint fib := by intro c _ d _ hcd rw [Function.onFun, Finset.disjoint_left] intro v hv hv' simp only [fib, Finset.mem_filter, Finset.mem_univ, true_and] at hv hv' exact hcd (hv.symm.trans hv') have hbij : S.biUnion fib = Finset.univ.filter fun v => top v ∈ S := by ext v simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and, fib] constructor · rintro ⟨c, hcS, htc⟩; rw [htc]; exact hcS · intro hv; exact ⟨top v, hv, rfl⟩ rw [← hbij, Finset.card_biUnion hdisj]
Every 3-candidate subset S satisfies 2 * ∑ c ∈ S, t c = n.
If |S| = 3, its complement Sᶜ in the 6-candidate universe also has size 6 - 3 = 3. By the balance assumption, 2 * ∑_{c ∈ S} t c ≤ n and 2 * ∑_{c ∈ Sᶜ} t c ≤ n. Because the two sums add up to ∑ c, t c = n, both inequalities must hold with equality.
uses
Finset.card_compl,Fintype.card_fin,Finset.sum_add_sum_complhave hS_eq : ∀ S : Finset (Fin 6), S.card = 3 → 2 * ∑ c ∈ S, t c = n := by intro S hS have hle1 : 2 * ∑ c ∈ S, t c ≤ n := by rw [← htop_card S]; exact hbal' S hS have hcomp : Sᶜ.card = 3 := by rw [Finset.card_compl, Fintype.card_fin] omega have hle2 : 2 * ∑ c ∈ Sᶜ, t c ≤ n := by rw [← htop_card Sᶜ]; exact hbal' Sᶜ hcomp have hsplit : ∑ c ∈ S, t c + ∑ c ∈ Sᶜ, t c = n := by rw [Finset.sum_add_sum_compl, hsum] omega
For any three distinct candidates a, b, c, 2 * (t a + t b + t c) = n.
Three distinct candidates form a subset {a, b, c} of cardinality 3. Unfolding the sum over this 3-element set and applying the previous equality for 3-candidate subsets yields 2 * (t a + t b + t c) = n.
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.sum_insert,Finset.sum_singletonhave htriple : ∀ a b c : Fin 6, a ≠ b → a ≠ c → b ≠ c → 2 * (t a + t b + t c) = n := by intro a b c hab hac hbc have hScard : ({a, b, c} : Finset (Fin 6)).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp [hbc] · simp [hab, hac] have h := hS_eq {a, b, c} hScard have hsum3 : ∑ x ∈ ({a, b, c} : Finset (Fin 6)), t x = t a + t b + t c := by rw [Finset.sum_insert (by simp [hab, hac]), Finset.sum_insert (by simp [hbc]), Finset.sum_singleton] omega rwa [hsum3] at h
Each candidate's count equals that of candidate 2: t 3 = t 2, t 0 = t 3, t 1 = t 3, t 4 = t 2, and t 5 = t 2.
Comparing pairs of 3-candidate sets that differ in only one element forces their unique elements to have equal voter counts. Specifically, comparing {0, 1, 2} to {0, 1, 3} gives t 3 = t 2; comparing {0, 1, 2} to {1, 2, 3} gives t 0 = t 3; comparing {0, 1, 2} to {0, 2, 3} gives t 1 = t 3; and comparing {0, 1, 2} to {0, 1, 4} and {0, 1, 5} gives t 4 = t 2 and t 5 = t 2 respectively.
have h32 : t 3 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 3 (by decide) (by decide) (by decide) omega have h03 : t 0 = t 3 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 1 2 3 (by decide) (by decide) (by decide) omega have h13 : t 1 = t 3 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 2 3 (by decide) (by decide) (by decide) omega have h42 : t 4 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 4 (by decide) (by decide) (by decide) omega have h52 : t 5 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 5 (by decide) (by decide) (by decide) omega
All six candidates have the same top-choice voter count: t c = t 2 for every c.
Exhaustive case analysis on c ∈ Fin 6 combines the pairwise equalities from the previous step to conclude that t c = t 2 for all six candidates.
have hconst : ∀ c : Fin 6, t c = t 2 := by intro c fin_cases c · show t 0 = t 2; rw [h03, h32] · show t 1 = t 2; exact h13.trans h32 · rfl · show t 3 = t 2; exact h32 · show t 4 = t 2; exact h42 · show t 5 = t 2; exact h52
The total voter sum across all candidates equals 6 * t 2.
Replacing each summand t c in the total sum with the equal constant t 2 yields a sum of 6 identical terms, which evaluates to 6 * t 2.
uses
Finset.sum_congr,Finset.sum_const,Fintype.card_finhave h6 : ∑ c : Fin 6, t c = 6 * t 2 := by rw [show ∑ c : Fin 6, t c = ∑ c : Fin 6, t 2 from Finset.sum_congr rfl fun c _ => hconst c] simp [Finset.sum_const, Fintype.card_fin]
Every candidate c is the top choice of exactly n/6 voters: 6 * t c = n.
For any candidate c, we have 6 * t c = 6 * t 2 = ∑ c, t c = n, which proves the theorem.
intro c show 6 * t c = n rw [hconst c, ← h6] exact hsum
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of its fibers under a function into another finite set.
Finset.card_univ- The cardinality of the universal finset of a finite type is the cardinality of the type itself.
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
Function.onFun- Defines a binary relation on elements by applying a given function to each element first; used here to formulate pairwise disjointness of voter fibers.
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 if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The logical simplification (True ∧ p) = p.
Finset.mem_biUnion- An element belongs to a finite indexed union if and only if it belongs to at least one set in the family.
Finset.card_biUnion- The cardinality of a pairwise disjoint finite union of finite sets is the sum of the individual cardinalities.
Finset.card_compl- The cardinality of the complement of a subset is the total number of elements in the finite type minus the cardinality of the subset.
Finset.sum_add_sum_compl- The sum of a function over a subset plus the sum over its complement equals the total sum over the entire finite type.
Finset.card_insert_of_notMem- Inserting an element into a finite set not already containing it increases the cardinality by 1.
Finset.card_singleton- A singleton finite set has cardinality 1.
Finset.sum_insert- The sum of a function over a set with a new element inserted equals the value at that element plus the sum over the original set.
Finset.sum_singleton- The sum of a function over a singleton set {a} is the value of the function at a.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
- The arithmetic condition 0 < 6 in the theorem statement is verified inline by `norm_num`.
- The deductions that complementary inequalities force an exact equality, and that overlapping triples imply equality of candidate voter counts, are discharged formally by Lean's `omega` tactic for linear integer arithmetic.
- Exhaustion of the six cases in Fin 6 is handled mechanically by `fin_cases`.
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.
/-- In the balanced regime with six candidates every candidate has exactly n/6 top-choice voters. -/theorem condorcet_six_balanced_top_structure (n : ℕ) (P : Fin n → Equiv.Perm (Fin 6)) (hbal : ∀ S : Finset (Fin 6), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ ∈ S).card ≤ n) : ∀ c : Fin 6, 6 * (Finset.univ.filter fun v => (P v).symm ⟨0, by norm_num⟩ = c).card = n := by classical let top : Fin n → Fin 6 := fun v => (P v).symm ⟨0, by norm_num⟩ let fib : Fin 6 → Finset (Fin n) := fun c => Finset.univ.filter fun v => top v = c let t : Fin 6 → ℕ := fun c => (fib c).card have hbal' : ∀ S : Finset (Fin 6), S.card = 3 → 2 * (Finset.univ.filter fun v => top v ∈ S).card ≤ n := hbal have hsum : ∑ c : Fin 6, t c = n := by have h := Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := top) (by intro a _; simp) simp only [Finset.card_univ, Fintype.card_fin] at h rw [← h] have htop_card : ∀ S : Finset (Fin 6), (Finset.univ.filter fun v => top v ∈ S).card = ∑ c ∈ S, t c := by intro S have hdisj : (↑S : Set (Fin 6)).PairwiseDisjoint fib := by intro c _ d _ hcd rw [Function.onFun, Finset.disjoint_left] intro v hv hv' simp only [fib, Finset.mem_filter, Finset.mem_univ, true_and] at hv hv' exact hcd (hv.symm.trans hv') have hbij : S.biUnion fib = Finset.univ.filter fun v => top v ∈ S := by ext v simp only [Finset.mem_biUnion, Finset.mem_filter, Finset.mem_univ, true_and, fib] constructor · rintro ⟨c, hcS, htc⟩; rw [htc]; exact hcS · intro hv; exact ⟨top v, hv, rfl⟩ rw [← hbij, Finset.card_biUnion hdisj] have hS_eq : ∀ S : Finset (Fin 6), S.card = 3 → 2 * ∑ c ∈ S, t c = n := by intro S hS have hle1 : 2 * ∑ c ∈ S, t c ≤ n := by rw [← htop_card S]; exact hbal' S hS have hcomp : Sᶜ.card = 3 := by rw [Finset.card_compl, Fintype.card_fin] omega have hle2 : 2 * ∑ c ∈ Sᶜ, t c ≤ n := by rw [← htop_card Sᶜ]; exact hbal' Sᶜ hcomp have hsplit : ∑ c ∈ S, t c + ∑ c ∈ Sᶜ, t c = n := by rw [Finset.sum_add_sum_compl, hsum] omega have htriple : ∀ a b c : Fin 6, a ≠ b → a ≠ c → b ≠ c → 2 * (t a + t b + t c) = n := by intro a b c hab hac hbc have hScard : ({a, b, c} : Finset (Fin 6)).card = 3 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · simp [hbc] · simp [hab, hac] have h := hS_eq {a, b, c} hScard have hsum3 : ∑ x ∈ ({a, b, c} : Finset (Fin 6)), t x = t a + t b + t c := by rw [Finset.sum_insert (by simp [hab, hac]), Finset.sum_insert (by simp [hbc]), Finset.sum_singleton] omega rwa [hsum3] at h have h32 : t 3 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 3 (by decide) (by decide) (by decide) omega have h03 : t 0 = t 3 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 1 2 3 (by decide) (by decide) (by decide) omega have h13 : t 1 = t 3 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 2 3 (by decide) (by decide) (by decide) omega have h42 : t 4 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 4 (by decide) (by decide) (by decide) omega have h52 : t 5 = t 2 := by have h1 := htriple 0 1 2 (by decide) (by decide) (by decide) have h2 := htriple 0 1 5 (by decide) (by decide) (by decide) omega have hconst : ∀ c : Fin 6, t c = t 2 := by intro c fin_cases c · show t 0 = t 2; rw [h03, h32] · show t 1 = t 2; exact h13.trans h32 · rfl · show t 3 = t 2; exact h32 · show t 4 = t 2; exact h42 · show t 5 = t 2; exact h52 have h6 : ∑ c : Fin 6, t c = 6 * t 2 := by rw [show ∑ c : Fin 6, t c = ∑ c : Fin 6, t 2 from Finset.sum_congr rfl fun c _ => hconst c] simp [Finset.sum_const, Fintype.card_fin] intro c show 6 * t c = n rw [hconst c, ← h6] exact hsum