condorcet_winning_set_of_bottom_three_majority
If S is a set of exactly three candidates and every candidate a outside S is ranked below all but at most two candidates by a strict majority of voters, then S is a Condorcet winning set.
Statement
theorem condorcet_winning_set_of_bottom_three_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.card = 3) (h : ∀ a, a ∉ S → n < 2 * (Finset.univ.filter fun v => (Finset.univ.filter fun c => P v a < P v c).card ≤ 2).card) : is_condorcet_winning_set P S
- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 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
To show that S is a Condorcet winning set, we must show that for any candidate a ∉ S, the set of voters bad who rank every candidate of S above a constitutes a strict minority, 2 * |bad| < n. For any voter in bad, all three candidates in S are ranked above a, so at least three candidates outrank a. However, the hypothesis guarantees a strict majority B of voters for whom at most two candidates outrank a, which makes bad and B disjoint. Since bad is disjoint from this majority B, their sizes satisfy |bad| + |B| ≤ n, which immediately implies 2 * |bad| < n.
Fix an arbitrary candidate a ∉ S and define the voter sets B and bad.
To show that S is a Condorcet winning set, we consider any candidate a not in S. We define B to be the set of voters v for whom at most two candidates c satisfy P(v)(a) < P(v)(c), and bad to be the set of voters v who rank every candidate b ∈ S above a, that is, P(v)(a) < P(v)(b) for all b ∈ S. By definition of a Condorcet winning set, it suffices to prove 2 * |bad| < n.
intro a ha let B := Finset.univ.filter (fun v : Fin n => (Finset.univ.filter fun c => P v a < P v c).card ≤ 2) let bad := Finset.univ.filter (fun v : Fin n => ∀ b ∈ S, P v a < P v b)
The sets bad and B are disjoint.
Using `Finset.disjoint_left`, we show that no voter v in bad can belong to B. For any v ∈ bad, every element b ∈ S satisfies P(v)(a) < P(v)(b), so S is a subset of the candidates ranked above a (`Finset.mem_filter`, `Finset.mem_univ`). By `Finset.card_le_card`, this implies that at least |S| = 3 candidates are ranked above a. However, any voter in B has at most 2 candidates ranked above a, which is an arithmetic contradiction 3 ≤ 2 resolved by `omega`.
uses
Finset.disjoint_left,Finset.mem_filter,Finset.mem_univ,Finset.card_le_cardhave h_disj : Disjoint bad B := by rw [Finset.disjoint_left] intro v hv rw [Finset.mem_filter] at hv ⊢ intro ⟨_, h2⟩ have h_sub : S ⊆ Finset.univ.filter (fun c => P v a < P v c) := by intro b hb rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hv.2 b hb⟩ have h_le := Finset.card_le_card h_sub rw [hS] at h_le omega
|bad| + |B| ≤ n.
Since bad and B are disjoint, the sum of their sizes equals the size of their union by `Finset.card_union_of_disjoint`. Because their union is a subset of the universe of all n voters (`Finset.card_le_univ` and `Fintype.card_fin`), its cardinality cannot exceed n.
uses
Finset.card_union_of_disjoint,Finset.card_le_univ,Fintype.card_finhave h_card_add : bad.card + B.card ≤ n := by have h_union : bad.card + B.card = (bad ∪ B).card := (Finset.card_union_of_disjoint h_disj).symm rw [h_union] have h_le := Finset.card_le_univ (bad ∪ B) simp only [Fintype.card_fin] at h_le exact h_le
2 * |bad| < n, completing the proof.
By the theorem's majority hypothesis h on a, the set B contains a strict majority of the voters, n < 2 * |B|. Combining this with |bad| + |B| ≤ n, linear arithmetic (`omega`) deduces 2 * |bad| < n, which establishes that S is a Condorcet winning set.
have hB : n < 2 * B.card := h a ha show 2 * bad.card < n omega
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_filter- An element belongs to the filter of a finite set by a predicate if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set `univ`.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the cardinality of the other set.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the type.
Fintype.card_fin- The cardinality of the type `Fin n` is n.
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.
/-- Dual of the top-choice cover: a 3-set is winning as soon as every outside candidate sits in the bottom three of a strict majority of voters. -/theorem condorcet_winning_set_of_bottom_three_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.card = 3) (h : ∀ a, a ∉ S → n < 2 * (Finset.univ.filter fun v => (Finset.univ.filter fun c => P v a < P v c).card ≤ 2).card) : is_condorcet_winning_set P S := by intro a ha let B := Finset.univ.filter (fun v : Fin n => (Finset.univ.filter fun c => P v a < P v c).card ≤ 2) let bad := Finset.univ.filter (fun v : Fin n => ∀ b ∈ S, P v a < P v b) have h_disj : Disjoint bad B := by rw [Finset.disjoint_left] intro v hv rw [Finset.mem_filter] at hv ⊢ intro ⟨_, h2⟩ have h_sub : S ⊆ Finset.univ.filter (fun c => P v a < P v c) := by intro b hb rw [Finset.mem_filter] exact ⟨Finset.mem_univ _, hv.2 b hb⟩ have h_le := Finset.card_le_card h_sub rw [hS] at h_le omega have h_card_add : bad.card + B.card ≤ n := by have h_union : bad.card + B.card = (bad ∪ B).card := (Finset.card_union_of_disjoint h_disj).symm rw [h_union] have h_le := Finset.card_le_univ (bad ∪ B) simp only [Fintype.card_fin] at h_le exact h_le have hB : n < 2 * B.card := h a ha show 2 * bad.card < n omega