condorcet_dimension_le_three_of_le_five
Every election with at most 5 candidates (and at least 1 voter) has a Condorcet winning set of at most 3 candidates.
Statement
theorem condorcet_dimension_le_three_of_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
(hn : 0 < n) (hm : m ≤ 5) :
∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- condorcet_winning_set_of_top_choice_majorityAny candidate set S whose complement contains the top choice of strictly fewer than n/2 voters (i.e. S contains the top choices of a…
- condorcet_dimension_le_three_of_le_fourEvery election with at most four candidates (and at least one voter) has a Condorcet winning set of at most three candidates: drop a…
- condorcet_balanced_top_implies_six_le_candidatesIf 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…
- 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…
The proof, explained
The proof splits into cases on the number of candidates m. For m ≤ 4, the claim holds by an earlier result. For m = 5, a helper theorem implies that if every 3-candidate subset had at most half the voters' top choices, there would have to be at least 6 candidates; hence some 3-candidate set S must contain the top choice of a strict majority of voters. Because a majority ranks a candidate in S first, no candidate outside S can beat all candidates in S by a majority, making S a Condorcet winning set.
The theorem holds when there are at most 4 candidates.
We perform a case split on whether m ≤ 4. If m ≤ 4, the result follows directly from the previously proved lemma condorcet_dimension_le_three_of_le_four.
uses
condorcet_dimension_le_three_of_le_fourby_cases hm4 : m ≤ 4 · exact condorcet_dimension_le_three_of_le_four n m P hn hm4
In the remaining case, the candidate count satisfies 4 ≤ m and 0 < m.
Since m ≤ 5 and the case m ≤ 4 has already been resolved, m must be 5, so in particular 4 ≤ m and m is positive.
have hm_ge4 : 4 ≤ m := by omega have hm_pos : 0 < m := by omega
It is false that every 3-candidate subset contains the top choice of at most half the voters.
We proceed by contradiction: assuming every 3-candidate subset contains the top choice of at most n / 2 voters, condorcet_balanced_top_implies_six_le_candidates would force m ≥ 6. But m ≤ 5, giving an arithmetic contradiction.
uses
condorcet_balanced_top_implies_six_le_candidateshave hbal : ¬ (∀ S : Finset (Fin m), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) := by intro h have h6 := condorcet_balanced_top_implies_six_le_candidates n m P hn hm_ge4 h omega
There exists a 3-candidate subset S whose members are the first choice of a strict majority of voters.
Negating the universal statement yields a set S of 3 candidates such that 2 · |{v | top(v) ∈ S}| > n.
push Not at hbal obtain ⟨S, hScard, hSgt⟩ := hbal
The number of voters whose top choice is in S and those whose top choice is outside S sum to n.
Partitioning the full voter set Fin n into those whose top choice is in S and those whose top choice is not via Finset.card_filter_add_card_filter_not, and simplifying using Finset.card_univ and Fintype.card_fin, gives an equality summing to n.
uses
Finset.card_filter_add_card_filter_not,Finset.card_univ,Fintype.card_finhave hpart := Finset.card_filter_add_card_filter_not (fun v => (P v).symm ⟨0, hm_pos⟩ ∈ S) (s := (Finset.univ : Finset (Fin n))) simp only [Finset.card_univ, Fintype.card_fin] at hpart
Strictly fewer than half of the voters have their top choice outside S.
Because strictly more than n / 2 voters have their top choice in S and the two groups sum to n, linear arithmetic (omega) establishes that 2 · |{v | top(v) ∉ S}| < n.
have h_not : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm_pos⟩ ∉ S).card < n := by omega
S is a Condorcet winning set of size at most 3.
We provide S as the required witness. Its cardinality is 3 (hence ≤ 3), and because strictly fewer than half the voters have their top choice outside S, condorcet_winning_set_of_top_choice_majority guarantees that S is a Condorcet winning set.
uses
condorcet_winning_set_of_top_choice_majorityrefine ⟨S, by omega, ?_⟩ exact condorcet_winning_set_of_top_choice_majority P hm_pos S h_not
condorcet_dimension_le_three_of_le_four- In an election with at least one voter and at most 4 candidates, there exists a Condorcet winning set of size at most 3.
condorcet_balanced_top_implies_six_le_candidates- In an election with at least one voter and at least 4 candidates, if every 3-candidate subset contains the first choice of at most half the voters, then there must be at least 6 candidates.
Finset.card_filter_add_card_filter_not- For any finite set and decidable predicate, the number of elements satisfying the predicate plus the number of elements satisfying its negation equals the cardinality of the set.
Finset.card_univ- The cardinality of the universal finset of a finite type is equal to the cardinality of that type.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
condorcet_winning_set_of_top_choice_majority- If strictly fewer than half of the voters have their top choice outside a candidate set S, then S is a Condorcet winning set.
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.
/-- Every election with at most five candidates has a Condorcet winning set of size at most three. -/theorem condorcet_dimension_le_three_of_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hm : m ≤ 5) : ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by by_cases hm4 : m ≤ 4 · exact condorcet_dimension_le_three_of_le_four n m P hn hm4 have hm_ge4 : 4 ≤ m := by omega have hm_pos : 0 < m := by omega have hbal : ¬ (∀ S : Finset (Fin m), S.card = 3 → 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) := by intro h have h6 := condorcet_balanced_top_implies_six_le_candidates n m P hn hm_ge4 h omega push Not at hbal obtain ⟨S, hScard, hSgt⟩ := hbal have hpart := Finset.card_filter_add_card_filter_not (fun v => (P v).symm ⟨0, hm_pos⟩ ∈ S) (s := (Finset.univ : Finset (Fin n))) simp only [Finset.card_univ, Fintype.card_fin] at hpart have h_not : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm_pos⟩ ∉ S).card < n := by omega refine ⟨S, by omega, ?_⟩ exact condorcet_winning_set_of_top_choice_majority P hm_pos S h_not