condorcet_winning_set_of_sum_min_rank_lt
If 2 * (sum of min ranks of S) < n, then S is a Condorcet winning set.
Statement
theorem condorcet_winning_set_of_sum_min_rank_lt {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.Nonempty) (h_sum : 2 * (∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _)) < n) : is_condorcet_winning_set P S
- Source
- step towards condorcet_dimension_le_three_balanced
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_sum_bad_outsiders_eq_sum_min_rankSumming the number of voters who rank an outsider candidate above all of S across all outsiders equals the sum across voters of the…
- 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
To show that S is a Condorcet winning set, we must show that for any outsider candidate a ∉ S, strictly fewer than n/2 voters prefer a to every candidate in S. The number of voters preferring a specific outsider a to all of S is bounded by the sum over all outsiders of the number of voters who prefer that outsider to S. By the identity condorcet_sum_bad_outsiders_eq_sum_min_rank, this total count of outsider-preferring voters equals the sum across all voters of the minimum rank of S. The hypothesis that twice this sum of minimum ranks is strictly less than n then immediately implies that twice the voter count for a is strictly less than n.
To show that S is a Condorcet winning set, it suffices to consider an arbitrary candidate a ∉ S, noting that a ∈ univ \ S.
By definition, S is a Condorcet winning set if for every candidate a ∉ S, twice the number of voters who prefer a to all candidates in S is strictly less than n. We introduce such an arbitrary candidate a with hypothesis ha : a ∉ S. Because a belongs to the universal set (Finset.mem_univ), it belongs to the complement Finset.univ \ S by Finset.mem_sdiff.mpr.
uses
Finset.mem_sdiff.mpr,Finset.mem_univintro a ha have ha' : a ∈ Finset.univ \ S := Finset.mem_sdiff.mpr ⟨Finset.mem_univ a, ha⟩
The number of voters preferring a to all of S is at most the total sum over all outsiders x ∈ univ \ S of the voters preferring x to all of S.
Since voter counts are non-negative natural numbers (Nat.zero_le), a single summand corresponding to a ∈ univ \ S is bounded above by the sum over the entire set of outsiders (Finset.single_le_sum).
uses
Finset.single_le_sum,Nat.zero_lehave h_le := @Finset.single_le_sum (Fin m) ℕ _ _ (fun x => (Finset.univ.filter (fun v => ∀ s ∈ S, P v x < P v s)).card) (Finset.univ \ S) _ (fun _ _ => Nat.zero_le _) a ha'
The sum over all outsiders x ∉ S of the count of voters preferring x to all of S equals the sum over all voters of their minimum rank of S.
This combinatorial identity is provided directly by the theorem condorcet_sum_bad_outsiders_eq_sum_min_rank.
uses
condorcet_sum_bad_outsiders_eq_sum_min_rankhave h_sum_eq := condorcet_sum_bad_outsiders_eq_sum_min_rank P S hSTwice the number of voters preferring a to all of S is strictly less than n, completing the proof.
We have that the voter count for a is bounded by the sum over outsiders, which equals the sum of minimum ranks across all voters. Since twice this sum of minimum ranks is strictly less than n by assumption, linear integer arithmetic (omega) finishes the proof.
omega
Finset.mem_sdiff.mpr- An element x belongs to the set difference s \ t if and only if x ∈ s and x ∉ t.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
Finset.single_le_sum- In a finite sum of non-negative elements, any individual summand is bounded above by the total sum.
Nat.zero_le- Every natural number is greater than or equal to zero.
condorcet_sum_bad_outsiders_eq_sum_min_rank- For any nonempty set of candidates S, the sum over all outsiders x ∉ S of the number of voters ranking x ahead of all candidates in S equals the sum across all voters of the minimum rank assigned to S.
- In this formalization, voter preferences are represented by permutations where smaller values indicate higher preference (rank 0 is the top choice). Consequently, voter v prefers candidate x to candidate y when P(v)(x) < P(v)(y).
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.
/-- If the sum of minimum ranks of S across all voters is strictly less than n/2, then S is a Condorcet winning set. -/theorem condorcet_winning_set_of_sum_min_rank_lt {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.Nonempty) (h_sum : 2 * (∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _)) < n) : is_condorcet_winning_set P S := by intro a ha have ha' : a ∈ Finset.univ \ S := Finset.mem_sdiff.mpr ⟨Finset.mem_univ a, ha⟩ have h_le := @Finset.single_le_sum (Fin m) ℕ _ _ (fun x => (Finset.univ.filter (fun v => ∀ s ∈ S, P v x < P v s)).card) (Finset.univ \ S) _ (fun _ _ => Nat.zero_le _) a ha' have h_sum_eq := condorcet_sum_bad_outsiders_eq_sum_min_rank P S hS omega