condorcet_dimension_le_three_of_voters_le_five
Every election with at most 5 voters (and at least 1 voter) has a Condorcet winning set of at most 3 candidates: selecting the top-choice candidate of each of the first min(n, 3) voters yields a winning set of size at most 3.
Statement
theorem condorcet_dimension_le_three_of_voters_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
(hn : 0 < n) (hn5 : n ≤ 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 2
- condorcet_winning_set_of_top_choicesFor any election with at least one candidate, the set of top-choice candidates of any subset of voters V0 is a Condorcet winning set…
- 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 handles elections with at most 5 voters by taking the set S of top-choice candidates of the first min(n, 3) voters (or the empty set if there are no candidates). The size of S is at most min(n, 3) ≤ 3 by construction. By an established criterion (condorcet_winning_set_of_top_choices), these top choices form a Condorcet winning set whenever the unrepresented voters do not form a majority (2 * (n - |V₀|) < n), which holds for all 1 ≤ n ≤ 5 by finite case check.
If there are no candidates (m = 0), the empty set is a Condorcet winning set of size at most 3.
We split into cases on whether m = 0. When there are no candidates, S = ∅ has size 0 ≤ 3, and the condition for being a Condorcet winning set holds vacuously because there are no candidates outside S in Fin 0.
uses
is_condorcet_winning_setby_cases hm : m = 0 · subst hm exact ⟨∅, by simp, by simp [is_condorcet_winning_set]⟩
When m > 0, we choose candidate set S as the top choices of the first min(n, 3) voters.
Since m ≠ 0, we have 0 < m by Nat.pos_of_ne_zero, so candidate 0 is well-defined. We define the voter subset V₀ = {v ∈ Fin n | v < 3} consisting of the first up to 3 voters, and propose S as the image of V₀ under each voter's top-choice candidate (P v)⁻¹(0). This leaves two goals: showing |S| ≤ 3 and that S is a Condorcet winning set.
uses
Nat.pos_of_ne_zero· have hm' : 0 < m := Nat.pos_of_ne_zero hm refine ⟨(Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).image (fun v => (P v).symm ⟨0, hm'⟩), ?_, ?_⟩
The proposed set S has cardinality at most 3.
By Finset.card_image_le, the size of S is bounded by the cardinality of V₀ = {v ∈ Fin n | v < 3}. Since 1 ≤ n ≤ 5, exhaustive case analysis on n shows that |V₀| = min(n, 3) ≤ 3 in every case.
uses
Finset.card_image_le· calc _ ≤ (Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).card := Finset.card_image_le _ ≤ 3 := by interval_cases n <;> decide
The proposed set S is a Condorcet winning set.
By condorcet_winning_set_of_top_choices, the top choices of voters V₀ form a Condorcet winning set if the remaining voters cannot form a majority, meaning 2 * (n - |V₀|) < n. We verify this inequality for each n ∈ {1, 2, 3, 4, 5} by case exhaustion: for n ≤ 3 the difference is 0; for n = 4 we have 2*(4-3) = 2 < 4; and for n = 5 we have 2*(5-3) = 4 < 5.
uses
condorcet_winning_set_of_top_choices· refine condorcet_winning_set_of_top_choices P hm' _ ?_ interval_cases n <;> decide
is_condorcet_winning_set- A candidate set S is a Condorcet winning set if every candidate outside S is strictly preferred to all candidates in S by strictly less than half of the voters.
Nat.pos_of_ne_zero- A natural number is strictly positive if it is non-zero.
Finset.card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the domain set.
condorcet_winning_set_of_top_choices- The set of top-choice candidates of a subset of voters V₀ is a Condorcet winning set provided that the remaining voters do not form a majority, that is, 2 * (n - |V₀|) < n.
- The arithmetic inequalities for the subset size and majority condition are verified by finite case exhaustion (`interval_cases n <;> decide`) over the five possible values n ∈ {1, 2, 3, 4, 5}.
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 5 voters and at least 1 voter has a Condorcet winning set of at most 3 candidates. -/theorem condorcet_dimension_le_three_of_voters_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hn5 : n ≤ 5) : ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by by_cases hm : m = 0 · subst hm exact ⟨∅, by simp, by simp [is_condorcet_winning_set]⟩ · have hm' : 0 < m := Nat.pos_of_ne_zero hm refine ⟨(Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).image (fun v => (P v).symm ⟨0, hm'⟩), ?_, ?_⟩ · calc _ ≤ (Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).card := Finset.card_image_le _ ≤ 3 := by interval_cases n <;> decide · refine condorcet_winning_set_of_top_choices P hm' _ ?_ interval_cases n <;> decide