condorcet_winning_set_of_top_choices
For any election with at least one candidate, the set of top-choice candidates of any subset of voters V0 is a Condorcet winning set provided that strictly fewer than n/2 voters lie outside V0.
Statement
theorem condorcet_winning_set_of_top_choices {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (hm : 0 < m) (V0 : Finset (Fin n)) (hV0 : 2 * (n - V0.card) < n) : is_condorcet_winning_set P (V0.image fun v => (P v).symm ⟨0, hm⟩)
- 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…
- Used by 1
- condorcet_dimension_le_three_of_voters_le_fiveEvery 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…
The proof, explained
To prove that the set S of top-choice candidates of voters in V0 forms a Condorcet winning set, we show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every member of S. No voter in V0 can prefer a to all of S, because S already contains their top-ranked candidate (rank 0), which cannot be strictly beaten. Therefore, all voters preferring a to every candidate in S must lie outside V0, limiting their count to at most |V0ᶜ| = n - |V0|. Since 2 * (n - |V0|) < n by hypothesis, strictly fewer than half of the voters prefer a to all candidates in S.
To show that the set of top choices 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 all candidates in S.
We introduce an arbitrary candidate a and the assumption ha that a does not belong to S = V0.image (fun v => (P v).symm ⟨0, hm⟩). By the definition of is_condorcet_winning_set, the remaining goal is to show that 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.
intro a haAny voter who strictly prefers candidate a to all candidates in S must belong to the complement of V0.
We prove that the set of voters preferring a to all b ∈ S is a subset of Finset.univ \ V0. Suppose for contradiction that such a voter v belongs to V0. Then voter v's top choice candidate (P v).symm ⟨0, hm⟩ is an element of S (via Finset.mem_image.mpr). Since v prefers a to every candidate in S, we have P v a < P v ((P v).symm ⟨0, hm⟩). By Equiv.apply_symm_apply, P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩, which implies P v a < 0. But in Fin m (where m is nonzero by Nat.pos_iff_ne_zero.mp), no element is strictly less than 0 (Fin.not_lt_zero), giving a contradiction. Membership in the complement is simplified using Finset.mem_filter, Finset.mem_univ, Finset.mem_sdiff, and true_and.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_sdiff,Finset.mem_image.mpr,Equiv.apply_symm_apply,Nat.pos_iff_ne_zero.mp,Fin.not_lt_zerohave hsub : (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b) ⊆ Finset.univ \ V0 := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] intro hvV have htop : (P v).symm ⟨0, hm⟩ ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩) := Finset.mem_image.mpr ⟨v, hvV, rfl⟩ have hlt := hv _ htop have hzero : P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩ := Equiv.apply_symm_apply _ _ rw [hzero] at hlt haveI : NeZero m := ⟨Nat.pos_iff_ne_zero.mp hm⟩ exact Fin.not_lt_zero (P v a) hlt
The number of voters who prefer candidate a to all candidates in S is at most n - |V0|.
By subset monotonicity of cardinality (Finset.card_le_card), the number of such voters is bounded by |univ \ V0|. Since univ \ V0 is the complement V0ᶜ, its size is |Fin n| - |V0| = n - |V0|, using Finset.card_compl and Fintype.card_fin.
uses
Finset.card_le_card,Finset.card_compl,Fintype.card_finhave hcard : (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card ≤ n - V0.card := by calc (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card ≤ (Finset.univ \ V0).card := Finset.card_le_card hsub _ = n - V0.card := by rw [show Finset.univ \ V0 = V0ᶜ by ext; simp] rw [Finset.card_compl, Fintype.card_fin]
Twice the number of voters who prefer candidate a to all candidates in S is strictly less than n.
The number of such voters is at most n - |V0|, and the assumption hV0 states that 2 * (n - |V0|) < n. Linear integer arithmetic closes the goal.
omega
Equiv.apply_symm_apply- Applying an equivalence to the image of an element under its inverse yields the original element: e (e.symm x) = x.
Fin.not_lt_zero- In Fin n, no element is strictly less than zero.
Finset.card_compl- The cardinality of the complement of a subset s in a finite type is the cardinality of the type minus the cardinality of s.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_image.mpr- An element belongs to the image of a set under a function if it is the image of some element in that set.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Fintype.card_fin- The cardinality of Fin n is n.
Nat.pos_iff_ne_zero.mp- If a natural number is strictly positive, then it is nonzero.
true_and- Conjunction with True is equivalent to the proposition itself: (True ∧ p) = p.
- In this formalization, a voter's preference ranking is modeled as a permutation where a smaller index denotes a higher preference: index 0 is the voter's top choice, so (P v).symm ⟨0, hm⟩ is voter v's most preferred candidate. The condition P v a < P v b means voter v strictly prefers candidate a over candidate 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.
/-- The set of top-choice candidates of a voter subset V0 is a Condorcet winning set if strictly fewer than n/2 voters lie outside V0. -/theorem condorcet_winning_set_of_top_choices {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (hm : 0 < m) (V0 : Finset (Fin n)) (hV0 : 2 * (n - V0.card) < n) : is_condorcet_winning_set P (V0.image fun v => (P v).symm ⟨0, hm⟩) := by intro a ha have hsub : (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b) ⊆ Finset.univ \ V0 := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] intro hvV have htop : (P v).symm ⟨0, hm⟩ ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩) := Finset.mem_image.mpr ⟨v, hvV, rfl⟩ have hlt := hv _ htop have hzero : P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩ := Equiv.apply_symm_apply _ _ rw [hzero] at hlt haveI : NeZero m := ⟨Nat.pos_iff_ne_zero.mp hm⟩ exact Fin.not_lt_zero (P v a) hlt have hcard : (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card ≤ n - V0.card := by calc (Finset.univ.filter fun v => ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card ≤ (Finset.univ \ V0).card := Finset.card_le_card hsub _ = n - V0.card := by rw [show Finset.univ \ V0 = V0ᶜ by ext; simp] rw [Finset.card_compl, Fintype.card_fin] omega