condorcet_winning_set_of_top_choice_majority
Any 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 strict majority of voters) is a Condorcet winning set.
Statement
theorem condorcet_winning_set_of_top_choice_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (hm : 0 < m) (S : Finset (Fin m)) (hS : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S).card < n) : is_condorcet_winning_set P S
- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- outside_voters_subset_top_choices_complFor any candidate set S and candidate x, any voter who ranks x strictly above every member of S has their top-choice candidate outside S.
- Used by 1
- condorcet_dimension_le_three_of_le_fiveEvery election with at most 5 candidates (and at least 1 voter) has a Condorcet winning set of at most 3 candidates.
The proof, explained
To prove that S is a Condorcet winning set, we must show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every member of S. Any voter who prefers a over every candidate in S cannot have their top-ranked candidate in S, meaning such voters are a subset of those whose top choice lies outside S. Since by assumption strictly fewer than n/2 voters have their top choice outside S, the number of voters preferring a to all of S is also strictly less than n/2.
To show that S is a Condorcet winning set, it suffices to show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every candidate in S.
Unfolding the definition of is_condorcet_winning_set, we introduce an arbitrary candidate a and the assumption _ha that a ∉ S. The goal becomes showing that 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.
intro a _haThe number of voters who prefer a to every candidate in S is at most the number of voters whose top choice is outside S.
By outside_voters_subset_top_choices_compl, any voter who ranks a ahead of all elements of S cannot have their top choice in S, so the set of such voters is a subset of {v | (P v).symm ⟨0, hm⟩ ∉ S}. Applying Finset.card_le_card then establishes that the cardinality of the former set is at most the cardinality of the latter.
uses
outside_voters_subset_top_choices_compl,Finset.card_le_cardhave hsub := outside_voters_subset_top_choices_compl P S a hm have hcard := Finset.card_le_card hsub
Twice the number of voters preferring a to all of S is strictly less than n, completing the proof.
The hypothesis hS guarantees that 2 * |{v | (P v).symm ⟨0, hm⟩ ∉ S}| < n. Combining this with the cardinality inequality hcard via linear integer arithmetic (omega) closes the goal 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.
omega
outside_voters_subset_top_choices_compl- The set of voters who strictly prefer candidate x to every candidate in S is a subset of the voters whose top choice is not in S.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
- Preferences of a voter v are represented as permutations of candidates where smaller values denote higher ranks: rank 0 is the top choice, given formally by (P v).symm ⟨0, hm⟩, and voter v prefers candidate a to b when P v a < P v b.
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.
/-- A candidate set containing the top choice of a strict majority of voters is a Condorcet winning set. -/theorem condorcet_winning_set_of_top_choice_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (hm : 0 < m) (S : Finset (Fin m)) (hS : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S).card < n) : is_condorcet_winning_set P S := by intro a _ha have hsub := outside_voters_subset_top_choices_compl P S a hm have hcard := Finset.card_le_card hsub omega