AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_of_le_four

theoremverifiedoriginal

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
Used by 1

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.

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

    lines 4–6

    uses Nat.lt_or_ge, condorcet_winning_set_univ

      classical
      rcases Nat.lt_or_ge m 4 with hm3 | hm4
      · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩
  2. 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.

    line 7

      obtain rfl : m = 4 := by omega
  3. 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`).

    lines 8–17

    uses Function.onFun, Finset.disjoint_left, Finset.mem_filter, Ne.symm, Finset.mem_univ, lt_irrefl

      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 _)
  4. 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`).

    lines 18–20

    uses Finset.card_biUnion, Finset.card_le_univ

      have hsum : ∑ a, (top a).card ≤ n := by
        rw [← Finset.card_biUnion hdisj]
        exact (Finset.card_le_univ _).trans (by simp)
  5. 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`).

    lines 21–27

    uses Finset.sum_le_sum, Finset.mul_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul

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

    lines 28–31

      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.

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

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