AFTD Auto-Formalizing Theoretical Domains

condorcet_ordering_certificate_excludes_common_obstruction

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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).

    lines 12–17

    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_fin

      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
  2. 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}.

    lines 18–24

    uses Finset.sum_comm, Finset.sum_congr, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, Nat.cast_id, Nat.mul_comm

      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]
  3. 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.

    lines 25–29

      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⟩
  4. 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.

    lines 30–35

    uses Finset.sum_mul, Finset.mul_sum, Finset.sum_le_sum, Nat.mul_le_mul_left

      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
  5. 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.

    line 36

      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.

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

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
See it in the graphDiscuss this resultChallenge it