condorcet_winning_family_of_subset_potentials_odd
Fix a relation R on the candidates. Suppose every outside-challenger selector whose roots are R-related to all committee members has natural claim weights of positive total and a natural subset potential with all local removal inequalities and full-set cost at most half the total weight. Then every positive odd electorate whose strict pairwise-majority edges are contained in R has a strict Condorcet winning committee in that family. Certificate existence remains a hypothesis. No additional properties of R are assumed; one may choose the actual majority tournament.
Statement
theorem condorcet_winning_family_of_subset_potentials_odd (m q : ℕ) (S : Fin q → Finset (Fin m)) (R : Fin m → Fin m → Prop) (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) → (∀ i,∀ c∈S i,R (f i) c) → ∃ (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ), (∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+H (A.erase a) ≤ H A) ∧ 0 < (∑ i,w i) ∧ 2*H univ ≤ ∑ i,w i) : ∀ (n : ℕ) (hn : 0<n) (hodd : Odd n) (P : Fin n → Equiv.Perm (Fin m)) (hR : ∀ a b, n < 2*(univ.filter fun v => P v a < P v b).card → R a b), ∃ i,is_condorcet_winning_set P (S i)
- Source
- IN-341 generic verification helper for the OP-19 odd-electorate route and the known odd-three-to-universal-four reduction. It weakens the certificate threshold to a non-strict half only when the electorate is odd. No universal certificate construction, new dimension bound, or research advance is claimed. Original strict definition: https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf .
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_ordering_score_le_subset_potentialFor any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining…
- 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 argues by contradiction: if no committee S i is a Condorcet winner, every committee admits an outside challenger f i ∉ S i preferred to all of S i by at least half the voters, which in an odd electorate gives a strict pairwise majority against each member of S i. The certificate hypothesis then provides positive-sum weights w and a subset potential H satisfying 2 * H univ ≤ ∑ i, w i. Double-counting the total voter score across voters and committees yields an upper bound of n * ∑ i, w i (since each voter's score is bounded by H univ) and a lower bound of (n + 1) * ∑ i, w i (since each challenger defeats their committee on at least (n + 1)/2 voters). Comparing the two bounds forces (n + 1) * ∑ i, w i ≤ n * ∑ i, w i, which contradicts the positivity of the total weight.
We assume for contradiction that no committee S i in the family is a Condorcet winning set.
Under classical logic, we introduce the electorate size n, its positivity and oddness, the preference profile P, and the relation condition hR. We then assume for contradiction (`by_contra hnone`) that none of the committees S i is a Condorcet winning set.
classical intro n hn hodd P hR by_contra hnone
There exists a challenger function f selecting for each committee S i an outside candidate f i ∉ S i preferred to all members of S i by at least n/2 voters.
For each index i, since S i is not a Condorcet winning set, unfolding the definition and pushing negations shows there is some candidate a ∉ S i such that n ≤ 2 * |{v | ∀ c ∈ S i, P v a < P v c}|. Applying the axiom of choice (`choose`) yields a selection function f with f i ∉ S i and this majority condition for every i.
have hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧ n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by intro i have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩ unfold is_condorcet_winning_set at hi push_neg at hi exact hi choose f hf hmaj using hbad
The challenger f i is R-related to every committee member c ∈ S i: R (f i) c holds for all i and c ∈ S i.
Any voter who ranks f i ahead of all members of S i in particular ranks f i ahead of c, so {v | ∀ b ∈ S i, P v (f i) < P v b} ⊆ {v | P v (f i) < P v c}. By monotonicity of cardinality (`Finset.card_le_card`), the latter set is at least as large. Since n is odd (n = 2k + 1) and n ≤ 2 * |{v | ∀ b ∈ S i, P v (f i) < P v b}|, linear integer arithmetic (`omega`) implies n < 2 * |{v | P v (f i) < P v c}|. The hypothesis hR then implies R (f i) c.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_cardhave hRel : ∀ i, ∀ c ∈ S i, R (f i) c := by intro i c hc apply hR have hsub : (univ.filter fun v => ∀ b ∈ S i, P v (f i) < P v b) ⊆ (univ.filter fun v => P v (f i) < P v c) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ exact hv c hc have hcard := Finset.card_le_card hsub have hm := hmaj i obtain ⟨k, hk⟩ := hodd omega
There exist claim weights w of positive total sum and a subset potential H satisfying the step inequalities and 2 * H univ ≤ ∑ i, w i.
Because f i ∉ S i and R (f i) c holds for all c ∈ S i, we invoke the certificate hypothesis hcert on f to obtain the weights w and subset potential H.
obtain ⟨w, H, hstep, hpos, hH⟩ := hcert f hf hRelThe sum of all voter scores equals the weighted sum over committees of the number of voters who prefer the challenger to the committee.
We define the score of a voter v as the sum of w i over all committees S i whose members are all ranked below f i by v. Exchanging the order of summation (`Finset.sum_comm`) and rewriting each inner sum over voters as a cardinality times w i, we obtain ∑ v, score v = ∑ i, w i * |{v | ∀ c ∈ S i, P v (f i) < P v c}|.
uses
Finset.sum_comm,Finset.sum_congr,Finset.sum_filter,Finset.sum_const,nsmul_eq_mul,Nat.cast_id,Nat.mul_commlet score : Fin n → ℕ := fun v => ∑ i, if ∀ c ∈ S i, P v (f i) < P v c then w i else 0 have hid : (∑ v, score v) = ∑ i, w i * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by dsimp only [score] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i _ rw [← Finset.sum_filter] simp only [Finset.sum_const, nsmul_eq_mul, Nat.cast_id, Nat.mul_comm]
The total score satisfies the upper bound 2 * (∑ v, score v) ≤ n * (∑ i, w i).
By lemma `condorcet_ordering_score_le_subset_potential`, each voter's score is at most H univ. Summing over the n voters gives ∑ v, score v ≤ n * H univ. Multiplying by 2 and applying the certificate property 2 * H univ ≤ ∑ i, w i yields 2 * (∑ v, score v) ≤ 2 * (n * H univ) = n * (2 * H univ) ≤ n * (∑ i, w i).
uses
condorcet_ordering_score_le_subset_potential,Finset.sum_le_sum,Nat.mul_le_mul_lefthave hscore : ∀ v, score v ≤ H univ := fun v => condorcet_ordering_score_le_subset_potential m q S f w H hstep (P v) have hupp : 2 * (∑ v, score v) ≤ n * (∑ i, w i) := by have h1 : (∑ v, score v) ≤ n * H univ := by calc (∑ v, score v) ≤ ∑ _v : Fin n, H univ := Finset.sum_le_sum (fun v _ => hscore v) _ = n * H univ := by simp calc 2 * (∑ v, score v) ≤ 2 * (n * H univ) := Nat.mul_le_mul_left 2 h1 _ = n * (2 * H univ) := by ring _ ≤ n * (∑ i, w i) := Nat.mul_le_mul_left n hH
The total score satisfies the lower bound (n + 1) * (∑ i, w i) ≤ 2 * (∑ v, score v).
Using the rewritten formula for the total score, for each committee i, since n is odd and n ≤ 2 * card, we have n + 1 ≤ 2 * card by arithmetic (`omega`). Multiplying by w i and summing over all i gives (n + 1) * (∑ i, w i) ≤ 2 * (∑ v, score v).
uses
Finset.mul_sum,Finset.sum_le_sum,Nat.mul_le_mul_righthave hlow : (n+1) * (∑ i, w i) ≤ 2 * (∑ v, score v) := by rw [hid] simp only [Finset.mul_sum] apply Finset.sum_le_sum intro i _ have hm := hmaj i obtain ⟨k, hk⟩ := hodd have h1 : n+1 ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by omega have h2 := Nat.mul_le_mul_right (w i) h1 calc (n+1) * w i ≤ (2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card) * w i := h2 _ = 2 * (w i * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card) := by ring
A contradiction is reached, proving that at least one committee S i is a Condorcet winning set.
Chaining the lower and upper bounds via transitivity (`le_trans`) yields (n + 1) * (∑ i, w i) ≤ n * (∑ i, w i). Since the total weight ∑ i, w i is strictly positive, right cancellation (`Nat.le_of_mul_le_mul_right`) implies n + 1 ≤ n, which `omega` recognises as impossible.
uses
le_trans,Nat.le_of_mul_le_mul_righthave hle : (n+1) * (∑ i, w i) ≤ n * (∑ i, w i) := le_trans hlow hupp have := Nat.le_of_mul_le_mul_right hle hpos omega
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `univ`.
true_and- The conjunction of True with any proposition p is equivalent to p.
Finset.card_le_card- If s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.sum_comm- The order of summation in a double finite sum can be interchanged.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their terms agree on all indices.
Finset.sum_filter- Summing a term over a filtered subset equals summing over the whole set with an indicator function testing the condition.
Finset.sum_const- Summing a constant over a finite set equals the cardinality of the set scalar-multiplied by that constant.
nsmul_eq_mul- Scalar multiplication by a natural number equals ordinary multiplication in a semiring.
Nat.cast_id- The coercion of a natural number to itself is the identity.
Nat.mul_comm- Multiplication of natural numbers is commutative.
condorcet_ordering_score_le_subset_potential- Under the local removal inequalities, the score of any linear ordering is at most the potential of the full candidate set.
Finset.sum_le_sum- A finite sum of smaller or equal terms is less than or equal to the sum of the larger terms.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality.
Finset.mul_sum- Multiplication distributes over finite sums from the left.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers by a factor on the right preserves the inequality.
le_trans- The less-than-or-equal relation is transitive.
Nat.le_of_mul_le_mul_right- If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
- In an odd electorate of size n = 2k + 1, the arithmetic step deducing the strict inequality n < 2 * card from n ≤ 2 * card (line 36) and deducing n + 1 ≤ 2 * card (line 63) is automated by Lean's Presburger arithmetic solver `omega`.
- Lines 45-46 use multiple algebraic rewrites (`sum_filter`, `sum_const`, `nsmul_eq_mul`, `cast_id`, `mul_comm`) as formal bookkeeping to convert a sum of indicator values into the product of the weight and the subset cardinality.
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 Finsettheorem condorcet_winning_family_of_subset_potentials_odd (m q : ℕ) (S : Fin q → Finset (Fin m)) (R : Fin m → Fin m → Prop) (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) → (∀ i,∀ c∈S i,R (f i) c) → ∃ (w : Fin q → ℕ) (H : Finset (Fin m) → ℕ), (∀ A : Finset (Fin m), ∀ a ∈ A, (∑ i, if f i=a ∧ S i ⊆ A.erase a then w i else 0)+H (A.erase a) ≤ H A) ∧ 0 < (∑ i,w i) ∧ 2*H univ ≤ ∑ i,w i) : ∀ (n : ℕ) (hn : 0<n) (hodd : Odd n) (P : Fin n → Equiv.Perm (Fin m)) (hR : ∀ a b, n < 2*(univ.filter fun v => P v a < P v b).card → R a b), ∃ i,is_condorcet_winning_set P (S i) := by classical intro n hn hodd P hR by_contra hnone have hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧ n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by intro i have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩ unfold is_condorcet_winning_set at hi push_neg at hi exact hi choose f hf hmaj using hbad have hRel : ∀ i, ∀ c ∈ S i, R (f i) c := by intro i c hc apply hR have hsub : (univ.filter fun v => ∀ b ∈ S i, P v (f i) < P v b) ⊆ (univ.filter fun v => P v (f i) < P v c) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ exact hv c hc have hcard := Finset.card_le_card hsub have hm := hmaj i obtain ⟨k, hk⟩ := hodd omega obtain ⟨w, H, hstep, hpos, hH⟩ := hcert f hf hRel let score : Fin n → ℕ := fun v => ∑ i, if ∀ c ∈ S i, P v (f i) < P v c then w i else 0 have hid : (∑ v, score v) = ∑ i, w i * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by dsimp only [score] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i _ rw [← Finset.sum_filter] simp only [Finset.sum_const, nsmul_eq_mul, Nat.cast_id, Nat.mul_comm] have hscore : ∀ v, score v ≤ H univ := fun v => condorcet_ordering_score_le_subset_potential m q S f w H hstep (P v) have hupp : 2 * (∑ v, score v) ≤ n * (∑ i, w i) := by have h1 : (∑ v, score v) ≤ n * H univ := by calc (∑ v, score v) ≤ ∑ _v : Fin n, H univ := Finset.sum_le_sum (fun v _ => hscore v) _ = n * H univ := by simp calc 2 * (∑ v, score v) ≤ 2 * (n * H univ) := Nat.mul_le_mul_left 2 h1 _ = n * (2 * H univ) := by ring _ ≤ n * (∑ i, w i) := Nat.mul_le_mul_left n hH have hlow : (n+1) * (∑ i, w i) ≤ 2 * (∑ v, score v) := by rw [hid] simp only [Finset.mul_sum] apply Finset.sum_le_sum intro i _ have hm := hmaj i obtain ⟨k, hk⟩ := hodd have h1 : n+1 ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by omega have h2 := Nat.mul_le_mul_right (w i) h1 calc (n+1) * w i ≤ (2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card) * w i := h2 _ = 2 * (w i * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card) := by ring have hle : (n+1) * (∑ i, w i) ≤ n * (∑ i, w i) := le_trans hlow hupp have := Nat.le_of_mul_le_mul_right hle hpos omega