condorcet_ordering_certificate_excludes_common_obstruction
For any finite family of challenger claims with nonnegative integer weights, if in every strict ranking their total satisfied weight is strictly less than half the total weight, no positive finite electorate can give all these claims at least half support.
Statement
theorem condorcet_ordering_certificate_excludes_common_obstruction (n m q : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (hcert : ∀ σ : Equiv.Perm (Fin m), 2 * (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) : ∃ i, 2 * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card < n
- Source
- Structural helpers for OP-19, following the strict definition in Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf , and the selector/ordering framework in arXiv:2604.19851v2. No new Condorcet dimension bound or research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- condorcet_winning_family_of_ordering_certificatesIf every outsider selector on a finite committee family admits nonnegative integer weights such that every strict ranking satisfies claims…
The proof, explained
The proof proceeds by contradiction using a double-counting (averaging) argument. For each voter, the certificate hypothesis guarantees that twice the weight of claims they satisfy is strictly less than the total weight; summing over all n voters implies that twice the sum of all voter scores is strictly less than n times the total weight. Conversely, if every claim received at least half support from the electorate, swapping the order of summation would force twice the total score to be at least n times the total weight, an immediate contradiction.
Twice the total score summed across all voters is strictly less than n times the total claim weight: 2 * (∑ v, score v) < n * (∑ i, w i).
For each voter v, define score(v) as the total weight of claims satisfied by v's ranking P(v). By the certificate hypothesis, 2 * score(v) < ∑ i, w i holds for every voter. Since n > 0, the electorate is nonempty (0 is a voter). Summing this strict inequality over all n voters and factoring constants out of the sums yields 2 * (∑ v, score v) < n * (∑ i, w i).
uses
mem_univ,Finset.sum_lt_sum_of_nonempty,Finset.mul_sum,Finset.sum_const,nsmul_eq_mul,Nat.cast_id,card_univ,Fintype.card_finclassical let score : Fin n → ℕ := fun v => ∑ i, if ∀ c ∈ S i, P v (f i) < P v c then w i else 0 have hne : (univ : Finset (Fin n)).Nonempty := ⟨⟨0,hn⟩,mem_univ _⟩ have hu := Finset.sum_lt_sum_of_nonempty hne (fun v _ => hcert (P v)) have hu' : 2*(∑ v, score v) < n*(∑ i, w i) := by simpa only [score,← Finset.mul_sum,Finset.sum_const,nsmul_eq_mul,Nat.cast_id,card_univ,Fintype.card_fin] using hu
The total score across all voters equals the sum over all claims of the claim's weight multiplied by the number of voters who satisfy it: ∑ v, score v = ∑ i, w i * #{v | P v satisfies claim i}.
Unfolding the definition of score(v) expresses the total score as a double sum over voters and claims. Interchanging the order of summation and collecting the indicator conditions rewrites the sum over voters for each claim i into the constant w i summed over the subset of voters satisfying claim i, which evaluates to w i * #{v | P v satisfies claim i}.
uses
Finset.sum_comm,Finset.sum_congr,Finset.sum_filter,Finset.sum_const,nsmul_eq_mul,Nat.cast_id,Nat.mul_commhave hid : (∑ v, score v) = ∑ i, w i * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by dsimp [score] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i hi rw [← Finset.sum_filter] simp only [Finset.sum_const,nsmul_eq_mul,Nat.cast_id,Nat.mul_comm]
Assuming no claim has support strictly less than n / 2, every claim i satisfies n ≤ 2 * #{v | P v satisfies claim i}.
We proceed by contradiction, assuming that no claim has support strictly below n / 2. For any claim i, if the inequality n ≤ 2 * #{v | P v satisfies claim i} failed, its negation would give 2 * #{v | P v satisfies claim i} < n, directly witnessing an excluded claim and contradicting the assumption.
by_contra hnone have hbad : ∀ i, n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by intro i by_contra hn' exact hnone ⟨i,by omega⟩
Under the contradiction hypothesis, n times the total weight is at most twice the total score: (∑ i, w i) * n ≤ 2 * (∑ v, score v).
Using the double-counting identity, twice the total score is ∑ i, 2 * (w i * #{v | P v satisfies claim i}), while (∑ i, w i) * n expands to ∑ i, w i * n. Multiplying the hypothesis n ≤ 2 * #{v | P v satisfies claim i} on the left by w i gives w i * n ≤ w i * (2 * #{v | P v satisfies claim i}) for each claim i. Summing these inequalities over all claims gives the desired lower bound.
uses
Finset.sum_mul,Finset.mul_sum,Finset.sum_le_sum,Nat.mul_le_mul_lefthave hl : (∑ i, w i)*n ≤ 2*(∑ v, score v) := by rw [hid,Finset.sum_mul,Finset.mul_sum] apply Finset.sum_le_sum intro i hi have h := Nat.mul_le_mul_left (w i) (hbad i) nlinarith
A contradiction is reached, completing the proof.
The upper bound 2 * (∑ v, score v) < n * (∑ i, w i) from the certificate and the lower bound (∑ i, w i) * n ≤ 2 * (∑ v, score v) from the contradiction assumption directly contradict each other, since n * (∑ i, w i) = (∑ i, w i) * n.
nlinarith
card_univ- The cardinality of `univ` on a finite type α equals `Fintype.card α`.
Fintype.card_fin- The cardinality of `Fin n` is n.
Finset.mul_sum- Multiplication on the left distributes over finite summation: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_comm- Finite double summations can be interchanged: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element.
Finset.sum_const- The sum of a constant value b over a finite set s equals |s| • b.
Finset.sum_filter- Summing f(a) over the subset where a predicate p holds equals summing the conditional expression (if p a then f a else 0) over the entire set.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Finset.sum_lt_sum_of_nonempty- Over a nonempty finite set, if each summand f(i) is strictly less than g(i), then ∑ i, f i < ∑ i, g i.
Finset.sum_mul- Multiplication on the right distributes over finite summation: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
mem_univ- Every element of a finite type belongs to its universal set `univ`.
Nat.cast_id- The canonical coercion from ℕ to ℕ is the identity function.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers n ≤ m on the left by k preserves the inequality: k * n ≤ k * m.
nsmul_eq_mul- Scalar multiplication of an element by a natural number n coincides with multiplication by n: n • a = n * a.
- To avoid rational arithmetic, the condition that total weight or voter support is strictly less than half is cleared of fractions and stated over ℕ as twice the quantity being strictly less than the total (e.g., 2 * score < total_weight).
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 2000000set_option maxRecDepth 10000theorem condorcet_ordering_certificate_excludes_common_obstruction (n m q : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)) (S : Fin q → Finset (Fin m)) (f : Fin q → Fin m) (w : Fin q → ℕ) (hcert : ∀ σ : Equiv.Perm (Fin m), 2 * (∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) : ∃ i, 2 * (univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card < n := by classical let score : Fin n → ℕ := fun v => ∑ i, if ∀ c ∈ S i, P v (f i) < P v c then w i else 0 have hne : (univ : Finset (Fin n)).Nonempty := ⟨⟨0,hn⟩,mem_univ _⟩ have hu := Finset.sum_lt_sum_of_nonempty hne (fun v _ => hcert (P v)) have hu' : 2*(∑ v, score v) < n*(∑ i, w i) := by simpa only [score,← Finset.mul_sum,Finset.sum_const,nsmul_eq_mul,Nat.cast_id,card_univ,Fintype.card_fin] using hu 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 [score] rw [Finset.sum_comm] apply Finset.sum_congr rfl intro i hi rw [← Finset.sum_filter] simp only [Finset.sum_const,nsmul_eq_mul,Nat.cast_id,Nat.mul_comm] by_contra hnone have hbad : ∀ i, n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v (f i) < P v c).card := by intro i by_contra hn' exact hnone ⟨i,by omega⟩ have hl : (∑ i, w i)*n ≤ 2*(∑ v, score v) := by rw [hid,Finset.sum_mul,Finset.mul_sum] apply Finset.sum_le_sum intro i hi have h := Nat.mul_le_mul_left (w i) (hbad i) nlinarith nlinarith