AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_family_of_subset_potentials_odd

theoremverified

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.

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

    lines 14–16

      classical
      intro n hn hodd P hR
      by_contra hnone
  2. 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.

    lines 17–24

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

    lines 25–36

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.card_le_card

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

    line 37

      obtain ⟨w, H, hstep, hpos, hH⟩ := hcert f hf hRel
  5. The 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}|.

    lines 38–46

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

      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]
  6. 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).

    lines 47–55

    uses condorcet_ordering_score_le_subset_potential, Finset.sum_le_sum, Nat.mul_le_mul_left

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

    lines 56–66

    uses Finset.mul_sum, Finset.sum_le_sum, Nat.mul_le_mul_right

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

    lines 67–69

    uses le_trans, Nat.le_of_mul_le_mul_right

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

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