AFTD Auto-Formalizing Theoretical Domains

condorcet_six_balanced_top_structure

theoremverified

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

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.

  1. 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.

    lines 4–11

          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
  2. 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.

    lines 12–16

    uses Finset.card_eq_sum_card_fiberwise, Finset.card_univ, Fintype.card_fin

      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]
  3. 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.

    lines 17–31

    uses Function.onFun, Finset.disjoint_left, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_biUnion, Finset.card_biUnion

      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]
  4. 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.

    lines 32–41

    uses Finset.card_compl, Fintype.card_fin, Finset.sum_add_sum_compl

      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
  5. 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.

    lines 42–54

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.sum_insert, Finset.sum_singleton

      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
  6. 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.

    lines 55–74

      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
  7. 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.

    lines 75–83

      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
  8. 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.

    lines 84–86

    uses Finset.sum_congr, Finset.sum_const, Fintype.card_fin

      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]
  9. 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.

    lines 87–90

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it