condorcet_dimension_le_four_of_odd_three
If every finite strict-ranking election with a positive odd number of voters has a strict Condorcet winning set of size at most three, then every finite strict-ranking election with a positive number of voters has one of size at most four. This is a conditional reduction, not a proof of either universal existence premise.
Statement
theorem condorcet_dimension_le_four_of_odd_three
(hodd : ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)),
0 < n → Odd n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) :
∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n →
∃ S : Finset (Fin m), S.card ≤ 4 ∧ is_condorcet_winning_set P S- Source
- IN-341 supporting reduction for the weaker universal-four target in OP-19. The remove-one-voter/add-that-voter-top-candidate argument is already in the proof of Proposition4 of Condorcet winning sets, Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . This helper is not new research.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 proceeds by case analysis on the parity of the number of voters n. If n is odd, the hypothesis directly yields a Condorcet winning set of size at most 3, which is also at most 4. If n is even (with n = k + 1 for positive odd k), the voter profile is split into the first k voters and the single final voter. Applying the hypothesis to the first k voters yields a winning set S of size at most 3, and adjoining the final voter's unique top choice c produces a set S ∪ {c} of size at most 4. Because the final voter cannot prefer any candidate to their own top choice c, any alternative candidate a ∉ S ∪ {c} can beat S ∪ {c} only among the first k voters, where the number of such voters is strictly less than k/2 < n/2, so S ∪ {c} is a winning set for the entire electorate.
If the number of voters n is odd, the election has a Condorcet winning set of size at most 4.
We introduce the parameters n, m, the profile P, and the assumption 0 < n, and split into cases based on whether n is odd. If n is odd, the hypothesis hodd immediately supplies a Condorcet winning set S with |S| ≤ 3. Since |S| ≤ 3 ≤ 4, S directly satisfies the goal.
intro n m P hn by_cases hodd_n : Odd n · obtain ⟨S, hSc, hSw⟩ := hodd n m P hn hodd_n exact ⟨S, by omega, hSw⟩
The case n = 0 is impossible, and if there are no candidates (m = 0), the empty set is a Condorcet winning set.
When n is not odd, n = 0 contradicts 0 < n. When n = k + 1, we case-split on m: if m = 0, the candidate set is empty, so the empty set ∅ has size 0 ≤ 4 and vacuously satisfies the winning condition via isEmptyElim since there are no candidates outside ∅.
uses
isEmptyElim· cases n with | zero => omega | succ k => cases m with | zero => refine ⟨∅, by simp, fun a _ => isEmptyElim a⟩ | succ m' =>
When n = k + 1 is positive and even, k is positive and odd.
Because k + 1 is not odd, Nat.not_odd_iff_even.mp establishes that k + 1 is even, so k + 1 = 2r for some r. The case r = 0 is impossible since k + 1 ≥ 1. For r = r' + 1 ≥ 1, we have k = 2r' + 1, which demonstrates by linear arithmetic that k > 0 and k is odd with witness r'.
uses
Nat.not_odd_iff_even.mphave heven : Even (k + 1) := Nat.not_odd_iff_even.mp hodd_n have hk_pos : 0 < k := by rcases heven with ⟨r, hr⟩ cases r with | zero => omega | succ r => omega have hk_odd : Odd k := by rcases heven with ⟨r, hr⟩ cases r with | zero => omega | succ r => refine ⟨r, by omega⟩
The union of a winning set of size at most 3 for the first k voters and the last voter's top choice has size at most 4.
Restricting P to the first k voters yields a sub-election P_prefix with an odd number k > 0 of voters. By the hypothesis hodd, this sub-election has a Condorcet winning set S with |S| ≤ 3. We let c be the candidate ranked first (rank 0) by the last voter (voter k). By Finset.card_insert_le, the set S ∪ {c} has cardinality at most |S| + 1 ≤ 4.
uses
Finset.card_insert_lelet P_prefix : Fin k → Equiv.Perm (Fin (m' + 1)) := fun i => P (Fin.castSucc i) obtain ⟨S, hSc, hSw⟩ := hodd k (m' + 1) P_prefix hk_pos hk_odd let c : Fin (m' + 1) := (P (Fin.last k)).symm 0 refine ⟨insert c S, by have := Finset.card_insert_le c S; omega, ?_⟩
For any alternative candidate a ∉ S ∪ {c}, the last voter does not rank a ahead of all candidates in S ∪ {c}.
Consider any candidate a ∉ S ∪ {c}. Then a ∉ S by Finset.mem_insert_of_mem. Let p(v) state that voter v prefers a to all of S ∪ {c}, and q(i) state that prefix voter i prefers a to all of S. For the last voter to satisfy p, they would have to rank a ahead of c (using Finset.mem_insert_self). However, c was chosen as the last voter's rank-0 choice (via Equiv.apply_symm_apply), which would imply that the rank of a is strictly negative, an impossibility for natural numbers.
uses
Finset.mem_insert_of_mem,Finset.mem_insert_self,Equiv.apply_symm_applyintro a ha have ha_S : a ∉ S := fun h => ha (Finset.mem_insert_of_mem h) have hSw_a := hSw a ha_S let p : Fin (k + 1) → Prop := fun v => ∀ b ∈ insert c S, P v a < P v b let q : Fin k → Prop := fun i => ∀ b ∈ S, P_prefix i a < P_prefix i b have hp_last : ¬ p (Fin.last k) := by intro h have hlt := h c (Finset.mem_insert_self c S) dsimp [c] at hlt rw [Equiv.apply_symm_apply] at hlt have : (P (Fin.last k) a).val < 0 := hlt omega
The number of voters among all k + 1 voters who prefer a to S ∪ {c} equals the number of such voters among the first k voters.
By Fin.univ_castSuccEmb and Finset.map_eq_image, the universe of all k + 1 voters is partitioned into the last voter and the embedding of the first k voters. Because the last voter does not satisfy p, Finset.filter_cons_of_neg removes them from the filtered set. By Finset.filter_map and Finset.card_map, the count of voters satisfying p across all k + 1 voters equals the count of prefix voters satisfying p ∘ Fin.castSucc.
uses
Finset.map_eq_image,Fin.univ_castSuccEmb,Finset.filter_cons_of_neg,Finset.filter_map,Finset.card_mapobtain ⟨h1, h2⟩ : ∃ (h : Fin.last k ∉ Finset.univ.map Fin.castSuccEmb), (Finset.univ : Finset (Fin (k + 1))) = Finset.cons (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h := ⟨by simp [Finset.map_eq_image], Fin.univ_castSuccEmb k⟩ have hp_eq : (Finset.univ.filter p).card = (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card := by rw [h2, Finset.filter_cons_of_neg p (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h1 hp_last, Finset.filter_map, Finset.card_map] rfl
Any prefix voter who prefers a to S ∪ {c} also prefers a to S.
By Finset.card_le_card, it suffices to prove set inclusion. If a prefix voter i ranks a ahead of every candidate in S ∪ {c}, then since every b ∈ S belongs to S ∪ {c} (via Finset.mem_insert_of_mem), voter i also ranks a ahead of every b ∈ S. Rewriting the membership conditions with Finset.mem_filter, Finset.mem_univ, and true_and completes the subset verification.
uses
Finset.card_le_card,Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_insert_of_memhave h_sub : (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card ≤ (Finset.univ.filter q).card := by apply Finset.card_le_card intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢ intro b hb exact hi b (Finset.mem_insert_of_mem hb)
Strictly fewer than half of the k + 1 voters prefer a to S ∪ {c}, establishing that S ∪ {c} is a Condorcet winning set.
The goal requires showing 2 * |{v : p(v)}| < k + 1. Combining the equality and inequality from previous steps gives |{v : p(v)}| ≤ |{i < k : q(i)}|. Because S was a Condorcet winning set for the prefix profile, we have 2 * |{i < k : q(i)}| < k. Linear integer arithmetic yields 2 * |{v : p(v)}| ≤ 2 * |{i < k : q(i)}| ≤ k - 1 < k + 1, completing the proof.
change 2 * (Finset.univ.filter p).card < k + 1 have : (Finset.univ.filter q).card = (Finset.univ.filter (fun v => ∀ b ∈ S, P_prefix v a < P_prefix v b)).card := rfl omega
isEmptyElim- From a term belonging to an empty type, any conclusion can be deduced (the principle of explosion for empty types).
Nat.not_odd_iff_even.mp- A natural number that is not odd is even.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Finset.mem_insert_of_mem- An element belonging to a set s also belongs to insert b s.
Finset.mem_insert_self- An element a belongs to insert a s.
Equiv.apply_symm_apply- Applying a permutation to the image of an element under its inverse returns the original element.
Finset.map_eq_image- Mapping a finite set under an embedding is equal to the image under the embedding's underlying function.
Fin.univ_castSuccEmb- The universal set of Fin (n + 1) decomposes into the singleton of the last element Fin.last n and the embedded image of Finset.univ for Fin n under Fin.castSuccEmb.
Finset.filter_cons_of_neg- Filtering a set extended by an element that does not satisfy predicate p gives the same result as filtering the original set.
Finset.filter_map- Filtering the mapped image of a set under an embedding equals mapping the subset filtered by the pull-back predicate.
Finset.card_map- An embedding between types preserves the cardinality of finite sets.
Finset.card_le_card- A subset of a finite set has cardinality less than or equal to the cardinality of the containing set.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
true_and- Conjunction of True with any proposition p is equivalent to p.
- The definition of `is_condorcet_winning_set` requires that for every alternative candidate a ∉ S, strictly fewer than half of the voters prefer a to all candidates in S (formalized as 2 * |{v : ∀ b ∈ S, P v a < P v b}| < n). Voters' preferences are strict rankings represented as permutations, where a lower numerical value indicates a higher preference (so rank 0 is the top choice).
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.
open Finsetopen scoped BigOperatorstheorem condorcet_dimension_le_four_of_odd_three (hodd : ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → Odd n → ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S) : ∀ (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), 0 < n → ∃ S : Finset (Fin m), S.card ≤ 4 ∧ is_condorcet_winning_set P S := by intro n m P hn by_cases hodd_n : Odd n · obtain ⟨S, hSc, hSw⟩ := hodd n m P hn hodd_n exact ⟨S, by omega, hSw⟩ · cases n with | zero => omega | succ k => cases m with | zero => refine ⟨∅, by simp, fun a _ => isEmptyElim a⟩ | succ m' => have heven : Even (k + 1) := Nat.not_odd_iff_even.mp hodd_n have hk_pos : 0 < k := by rcases heven with ⟨r, hr⟩ cases r with | zero => omega | succ r => omega have hk_odd : Odd k := by rcases heven with ⟨r, hr⟩ cases r with | zero => omega | succ r => refine ⟨r, by omega⟩ let P_prefix : Fin k → Equiv.Perm (Fin (m' + 1)) := fun i => P (Fin.castSucc i) obtain ⟨S, hSc, hSw⟩ := hodd k (m' + 1) P_prefix hk_pos hk_odd let c : Fin (m' + 1) := (P (Fin.last k)).symm 0 refine ⟨insert c S, by have := Finset.card_insert_le c S; omega, ?_⟩ intro a ha have ha_S : a ∉ S := fun h => ha (Finset.mem_insert_of_mem h) have hSw_a := hSw a ha_S let p : Fin (k + 1) → Prop := fun v => ∀ b ∈ insert c S, P v a < P v b let q : Fin k → Prop := fun i => ∀ b ∈ S, P_prefix i a < P_prefix i b have hp_last : ¬ p (Fin.last k) := by intro h have hlt := h c (Finset.mem_insert_self c S) dsimp [c] at hlt rw [Equiv.apply_symm_apply] at hlt have : (P (Fin.last k) a).val < 0 := hlt omega obtain ⟨h1, h2⟩ : ∃ (h : Fin.last k ∉ Finset.univ.map Fin.castSuccEmb), (Finset.univ : Finset (Fin (k + 1))) = Finset.cons (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h := ⟨by simp [Finset.map_eq_image], Fin.univ_castSuccEmb k⟩ have hp_eq : (Finset.univ.filter p).card = (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card := by rw [h2, Finset.filter_cons_of_neg p (Fin.last k) (Finset.univ.map Fin.castSuccEmb) h1 hp_last, Finset.filter_map, Finset.card_map] rfl have h_sub : (Finset.univ.filter (fun i : Fin k => p (Fin.castSucc i))).card ≤ (Finset.univ.filter q).card := by apply Finset.card_le_card intro i hi simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢ intro b hb exact hi b (Finset.mem_insert_of_mem hb) change 2 * (Finset.univ.filter p).card < k + 1 have : (Finset.univ.filter q).card = (Finset.univ.filter (fun v => ∀ b ∈ S, P_prefix v a < P_prefix v b)).card := rfl omega